2
$\begingroup$

Given a full row-rank matrix $A$, this can be put into a unique reduced row echelon form via elementary row operations. Allow column permutations (no column addition / multiplication) and this can be put in the form $$ (I|X). $$ This form is non-unique as different right-hand submatrices $X$ can be obtained from this procedure by permuting the columns of A before row reduction, or by permuting the columns of $(I|X)$, performing row reduction on the result and permuting columns again.

Is anything known about the sets of $X$ submatrices related to a full row-rank $A$ in this way? I'm sure this has been studied somewhere but it's a somewhat difficult topic to search for. I'm particularly interested in the case for matrices over $\mathbb{F}_2$.

Improve this question
$\endgroup$
4
  • $\begingroup$ The reduced row echelon form is unique, so you may as well start there. You can apply an arbitrary permutation of rows, apply the inverse permutation on the first block of columns to recover the identity matrix, and then apply an arbitrary permutation to the remaining columns. So I guess that $X$ is determined up to arbitrary permutation of rows and columns. Deciding whether given $X_{1}$ and $X_{2}$ are equivalent under this operation is more-or-less isomorphism of bipartite graphs. $\endgroup$
    – Padraig Ó Catháin
    Commented May 24 at 15:41
  • $\begingroup$ This is true, thank you, although I'm more interested in the $X$s that are inequivalent up to these moves. You can take a row which has a 1 in some column in the right half, add it to all other rows with a 1 in that column -- turning that column into a one-entry vector -- then normalise it and swap it to the left half to restore the $I$ block. $\endgroup$
    – DeafIdiotGod
    Commented May 24 at 16:17
  • 1
    $\begingroup$ Ah - that's true. I'm not aware of any literature about this equivalence operation on rectangular matrices. Are you aware of any invariants of $X$ that are preserved? $\endgroup$
    – Padraig Ó Catháin
    Commented May 24 at 16:36
  • $\begingroup$ Honestly I'm having trouble finding any! The rank of $X$ is unpreserved in general, consider the case over $\mathbb{F}_2$ where $X$ is all ones except for the diagonal which is 0, this has rank 2. With $(I|X)$ add row 1 to row 3 then swap columns 1 and 6 to obtain $(I|X')$ where $X'$ is now rank 3. $\endgroup$
    – DeafIdiotGod
    Commented May 28 at 11:29

1 Answer 1

Reset to default
1
$\begingroup$

Let $A$ be an $n \times m$ matrix over $k$. Since the group $\textrm{GL}_{n}(k)$ acts transitively on the ordered bases of an $n$-dimensional $k$-vector space, any $n$ linearly independent columns of $A$ can be mapped onto the standard basis vectors. Under the action of the symmetric group on columns, these can be placed in the first $n$ columns if desired (but I think it's a distraction for answering the question).

I think that the linear dependencies between columns are all that matters. What you would like to study is the matroid associated with the collection of column vectors. I would guess that the number of choices for the matrix $X$ up to equivalence is equal to the number of matroids representable over the field $k$ as a full-rank matrix with $n$ rows and $m$ columns. I'm not an expert in matroid theory, but I think that questions of this type have been studied (and closed form formulas probably don't exist).

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is as good an answer as I can hope for at the moment, thank you. $\endgroup$
    – DeafIdiotGod
    Commented Jun 3 at 9:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .