{"id":6280,"date":"2026-09-07T15:16:55","date_gmt":"2026-09-07T19:16:55","guid":{"rendered":"https:\/\/matroidunion.org\/?p=6280"},"modified":"2026-09-07T15:16:57","modified_gmt":"2026-09-07T19:16:57","slug":"representable-matroid-lifts","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=6280","title":{"rendered":"Representable Matroid Lifts"},"content":{"rendered":"\n

In this blog post, I’m going to discuss a part of a paper I wrote with Zach Walsh a few years back called “Matroid lifts and representability.” We’ll start by motivating the idea of a\u00a0<\/em>matroid\u00a0lift.<\/em><\/p>\n

Let $A \\in \\mathbb{F}^{r_1 \\times n}$ and $B \\in \\mathbb{F}^{r_2 \\times n}$ be matrices such that $A$ is a row-submatrix of $B$. Let $E$ denote the column set of $B$, which also naturally indexes the column set of $A$. Let $M_A$ and $M_B$ denote the matroids on ground set $E$ defined by linear independence in $A$ and $B$, respectively. Since $A$ is a row-submatrix of $B$, there is a special relationship between $M_A$ and $M_B$. In particular, every flat of $M_A$ is a flat of $M_B$. This motivates the following definition: given two matroids $M_1$ and $M_2$ on a common ground set $E$, one says that $M_2$ is a lift<\/em> of $M_1$ if every flat of $M_1$ is a flat of $M_2$.<\/p>\n

An Example<\/h1>\n

Recall that $U_{r,n}$ denotes the uniform matroid of rank $r$ on $n$ elements. One can check that $U_{2,3}$ is a lift of $U_{1,3}$. One can check this by noting that the flats of $U_{1,3}$ are the empty set, the full ground set, and each singleton set and that each of these are also flats of $U_{2,3}$. Alternatively, one can consider the following $\\mathbb{Q}$-matrix<\/p>\n

$\\begin{pmatrix} 1 & 1 & 1 \\\\ 0 & 1 & 2 \\end{pmatrix}$<\/p>\n

and note that the matroid of the top row is $U_{1,3}$ and the matroid of the whole matrix is $U_{2,3}$. One interesting thing to note is that even though $U_{1,3}$ and $U_{2,3}$ are both $\\mathbb{F}_2$-representable, there is no $2\\times 3$ $\\mathbb{F}_2$ matrix $B$ that represents $U_{2,3}$, whose top row represents $U_{1,3}$.<\/p>\n

Notational Remark<\/h1>\n

For any matroid $Q$, I will use the notation $r_Q$ and ${\\rm cl}_Q$ to denote the rank function and closure operator in $Q$.<\/p>\n

Elementary lifts<\/h1>\n

If $M_2$ is a lift of $M_1$, then the rank of $M_2$ is greater than or equal to that of $M_1$. When $M_2$ is a lift of $M_1$ whose rank is exactly one greater than that of $M_1$, one says that $M_2$ is an elementary<\/em> lift of $M_1$. I will now describe a classical theorem of Brylawski, the dual version of which was previously stated by Crapo, that gives an elegant combinatorial characterization of all elementary lifts of a matroid $M$.<\/p>\n

Let $M$ be a matroid on ground set $E$. A linear class of $M$<\/em> is a collection $\\mathcal{L}$ of circuits of $M$ such that if $C_1,C_2 \\in \\mathcal{L}$ satisfy<\/p>\n

$|C_1 \\cup C_2| – r_M(C_1 \\cup C_2) = 2$<\/p>\n

then if $C_3$ is a circuit of $M$ contained in $C_1 \\cup C_2$, then $C_3 \\in \\mathcal{L}$. For each such linear class, one can define a function $r_\\mathcal{L}: 2^{E} \\rightarrow \\mathbb{N}$ as follows<\/p>\n

$r_\\mathcal{L}(X) = \\begin{cases}r_M(X) & \\textnormal{if each circuit of } M|X \\textnormal{ is in } \\mathcal{L} \\\\ r_M(X) + 1 & {\\rm otherwise}.\\end{cases}$<\/p>\n

For each linear class $\\mathcal{L}$ of $M$, $r_\\mathcal{L}$ is the rank function of a matroid $L$ such that $L$ is an elementary lift of $M$. What is even more interesting is that for\u00a0every<\/em> elementary lift $L$ of $M$, there exists a linear class $\\mathcal{L}$ of circuits of $M$ such that the rank function of $L$ is $r_{\\mathcal{L}}$.<\/p>\n

Higher-rank lifts<\/h1>\n

I became aware of Zach’s existence when his paper “A new matroid lift construction and an application to group-labeled graphs” hit the arXiv. It gave a method for constructing non-elementary lifts of matroids in a way that generalized Brylawski’s construction. At the time, I was on the prowl for matroid theory tools that could be useful in rigidity theory, and matroid lifts had recently played a key role in a groundbreaking paper of Clinch, Jackson, and Tanigawa called “Abstract 3-Rigidity and Bivariate C12-Splines II: Combinatorial Characterization.” So I was very intrigued by Zach’s construction, which is given in the following theorem.\u00a0<\/p>\n

Theorem (Walsh):\u00a0<\/strong>Let $M$ be a matroid on ground set $E$ with circuit set $\\mathcal{C}$. Let $N$ be a matroid on ground set $\\mathcal{C}$ such that if $|C_1 \\cup C_2| – r_M(C_1 \\cup C_2) = 2$, then each $C \\in \\mathcal{C}$ such that $C \\subset C_1 \\cup C_2$ satisfies $C \\in {\\rm cl}_N(\\{C_1 \\cup C_2\\})$. Then the function $\\rho_N: 2^E \\rightarrow \\mathbb{N}$ defined as follows is the rank function of a lift of $M$ of rank $r_M(E) + r_N(\\mathcal{C})$<\/p>\n

$\\rho_N(X) = r_M(X) + r_N(\\{C : C \\textnormal{ is a circuit of } M|X\\}).$<\/p>\n

Zach’s construction generalizes Brylawski’s construction in the sense that when $r_N(\\mathcal{C}) = 1$, the rank-zero flat of $N$ is a linear class $\\mathcal{L}$ of circuits of $M$, and that $r_\\mathcal{L} = \\rho_N$. Zach had hoped that this construction would completely generalize Brylawski’s result in that every lift of a matroid $M$ would have rank function of the form $\\rho_N$ for some matroid $N$ on the circuit set of $M$. As we will see, this is not the case. However, it does<\/em> hold for matroid lifts that arise from taking the matroid of a matrix, and a row-submatrix. This gives us a way to test that a given lift is “representable” as a lift, and can even be turned into a test for matroid representability.<\/p>\n

Theorem (B-Walsh):\u00a0<\/strong>Let $A \\in \\mathbb{F}^{r_1 \\times n}$ and $B \\in \\mathbb{F}^{r_2 \\times n}$ such that $A$ is a row-submatrix of $B$. Let $M_A,M_B$ respectively denote the column matroids of $A$ and $B$ and let $\\mathcal{C}$ denote the set of circuits of $A$. Then there exists a matroid $N$ on ground set $\\mathcal{C}$ such that $\\rho_N$ is the rank function of $M_B$.<\/p>\n

Here is a sketch of the proof. Since $A$ is a row-submatrix of $B$ we may without loss of generality assume that $B$ has the following form for some matrix $C$<\/p>\n

$B = \\binom{A}{C}$.<\/p>\n

For each circuit $C$ of $M_A$ let $x_C$ be a fixed element of $\\mathbb{F}^n$ such that $Ax = 0$. Then $Bx_C$ can be written in the following form for some $x_C’ \\in \\mathbb{F}^{r_2-r_1}$<\/p>\n

$Bx_C = \\binom{0}{x_C’}$.<\/p>\n

This enables us to define a matroid $N$ on the circuit set $\\mathcal{C}$ of $A$ by asserting that $\\{C_1,\\dots,C_k\\}$ is independent in $N$ if and only if the set of vectors $\\{x_{C_1}’,\\dots,x_{C_k}’\\}$ is linearly independent in $\\mathbb{F}^{r_2-r_1}$. Then, the rank function of $M_B$ is $\\rho_N$.<\/p>\n

Non-representable higher rank lifts<\/h1>\n

The proof of the above theorem heavily depends on access to a linear representation of the higher rank matroid, that has a row-submatrix representing the lower rank matroid. This dependence on a representation cannot be avoided, at least not in full generality. In particular, we can obtain a counterexample from the V\u00e1mos matroid.<\/p>\n

Given any matroid $M$ on ground set $E$ and an independent subset $I \\subset E$, $M\\setminus I$ is always a lift of $M \/ I$ and the difference in ranks is $|I|$ and all lifts can be obtained in this way. Let $V_8$ be the matroid with ground set $\\{1,2,\\dots,8\\}$ of rank $4$, such that every subset of size four or smaller is independent, with the exceptions of the following four-element subsets<\/p>\n

$1234,3456,5678,1278,3478.$<\/p>\n

This is known as the V\u00e1mos<\/em> matroid, which is known to not be representable over any field. Then $V_8 \\setminus \\{7,8\\}$ is a lift of $V_8 \/ \\{7,8\\}$, and as Zach and I show in our paper, there is no matroid $N$ of rank $2$ on the circuit set of $V_8 \/ \\{7,8\\}$ such that the rank function of $V_8 \\setminus \\{7,8\\}$ is $\\rho_N$. We generalize this construction to construct a two-parameter infinite antichain (in the minor partial order) of sparse paving matroids that are not representable over any field, that satisfy Ingleton’s inequality.<\/p>\n

Concluding remarks<\/h1>\n

As with many papers I’ve written, the bulk of the time I spent “writing” this paper was spent chasing something I wound up being unable to prove. In particular, I was hoping to generalize the theorem about representable lifts of matroids being obtainable via Zach’s construction to the family of algebraic matroids. Alas, not only was I unable to prove that, I’m not so sure if it’s true anymore. But I really don’t have any reason to make a conjecture either way.<\/p>\n\n\n\n\n\n\n","protected":false},"excerpt":{"rendered":"

In this blog post, I’m going to discuss a part of a paper I wrote with Zach Walsh a few years back called “Matroid lifts and representability.” We’ll start by motivating the idea of a\u00a0matroid\u00a0lift. Let $A \\in \\mathbb{F}^{r_1 \\times … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":22,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-6280","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/6280","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/22"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=6280"}],"version-history":[{"count":19,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/6280\/revisions"}],"predecessor-version":[{"id":6299,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/6280\/revisions\/6299"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=6280"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=6280"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=6280"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}