Representability of Matroids by c-Arrangements is Undecidable

Understand

For a natural number $c$, a $c$-arrangement is an arrangement of dimension $c$ subspaces satisfying the following condition: the sum of any subset of the subspaces has dimension a multiple of $c$.

• Matroids arising as normalized rank functions of $c$-arrangements are also known as multilinear matroids.
• We prove that it is algorithmically undecidable whether there exists a $c$ such that a given matroid has a $c$-arrangement representation, or equivalently whether the matroid is multilinear.
• It follows that certain network coding problems are also undecidable.