11
$\begingroup$

This question was posed on MSE here three days ago, but hasn't gotten any answers or suggestions. I hope it's okay to ask it on MO, but if I should wait a little longer, please just let me know.

Say $M$ is a (finite) matrix with entries in your favorite field. Let $P$ be the collection of nonvanishing minors of $M$, ordered by inclusion in the natural way. The height of $P$ is the rank of $M$. What else can one say about $P$? For example, here are some naive questions:

  1. What is the width of $P$? (Does it have any natural meaning, like the height of $P$ being the rank of $M$?)
  2. Does $P$ have the Sperner property?
  3. What posets can be realized in this way? Does it depend on the field? What if we restrict to integer $0$-$1$ matrices?

For instance, $P$ can't be a linear order, except in the pretty trivial case that $M$ has at most one nonzero entry.

All the same questions can be asked for the poset of square submatrices of $M$ with nonzero permanent. The questions were inspired by this MO question.

Improve this question
$\endgroup$
5
  • $\begingroup$ Isn't what you're describing just a (realizable) matroid? $\endgroup$
    – Sam Hopkins
    Commented Dec 19, 2017 at 21:21
  • $\begingroup$ @SamHopkins I guess if you project the nonvanishing minors onto their column indices (or row indices) then you get the usual independence matroids. I'll think about that. But I don't think my poset is itself a matroid (or if it is, I don't see it). Thanks for your observation, but off the top of my head, I think it still leaves my questions open. $\endgroup$
    – Zach Teitler
    Commented Dec 19, 2017 at 21:38
  • 2
    $\begingroup$ The way I am used to getting a matroid in this situation is the following. Suppose for simplicity M is a nxn square matrix. Then consider the nx(2n) matrix M’ obtained by putting a nxn identity matrix in front of M. Then (up to sign, which shouldn’t matter here) the maximal minors of M’ correspond to all of the minors of M, and hence the nonvanishing minors of M correspond to the bases of the column matroid of M’. $\endgroup$
    – Sam Hopkins
    Commented Dec 19, 2017 at 22:10
  • 2
    $\begingroup$ But yes, you care about more here: the order on bases. I’m not sure exactly what this order is (it’s not just e.g. lexicographic order, as far as I can tell). $\endgroup$
    – Sam Hopkins
    Commented Dec 19, 2017 at 22:12
  • 1
    $\begingroup$ Perhaps, you want to check out the concept of linking systems due to A. Scrijver (1974). It is equivalent to matroids. $\endgroup$
    – Sang-il
    Commented Aug 5, 2020 at 14:23

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .