{"id":4970,"date":"2023-07-03T08:05:49","date_gmt":"2023-07-03T12:05:49","guid":{"rendered":"http:\/\/matroidunion.org\/?p=4970"},"modified":"2026-02-09T15:10:02","modified_gmt":"2026-02-09T20:10:02","slug":"matroid-lifts-and-representability","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=4970","title":{"rendered":"Matroid lifts and representability"},"content":{"rendered":"\n

1. Introduction<\/strong><\/p>\n\n\n\n

In this post I’ll highlight some new constructions related to matroid lifts as detailed in the recent papers [Wal22] and [BW23]. If a matroid $M$ is represented by a matrix $A$, one can naturally obtain a new matroid $L$ by adding rows to $A$ as in Figure 1.<\/p>\n\n\n

\n
\"\"<\/a>
Figure 1. <\/strong>$M(A’)$ is a lift of $M(A)$.<\/figcaption><\/figure><\/div>\n\n\n

Certainly $M$ and $L$ have a special relationship, which can be defined for general matroids as follows.<\/p>\n

Definition 1: <\/strong>Given matroids $M$ and $L$ on a common ground set $E$, we say that $L$ is a lift<\/em> of $M$ (and $M$ is a projection <\/em>or quotient <\/em>of $L$) if there exists a matroid $K$ on ground set $E \\cup F$ such that $M = K \/ F$ and $L = K \\setminus F$. We say that $L$ is a rank-$k$ lift<\/em> of $M$ if $r(L) – r(M) = k$.<\/p>\n

Continuing with the example in Figure 1, the matroid $K$ could be represented by the matrix obtained from $A’$ by appending the first $k$ unit column vectors. Rank-$1$ lifts, called elementary lifts<\/em>, are well understood. A classical theorem of Brylawski [Bry86], which was previously stated in the dual by Crapo [Cra65], says that elementary lifts of a matroid $M$ are in bijection with special sets of circuits of $M$.<\/p>\n

Theorem 1 (Crapo-Brylawski): <\/strong>Let $M$ be a matroid on ground set $E$ and let $\\mathcal C$ be a set of circuits of $M$ so that<\/p>\n