prove that $M\big[ \frac{A_1}{A_2}\big] = M[A_1].$

83 Views Asked by At

Here is the question I am trying to tackle:

For $i = 1,2,$ let $A_i$ be an $m_i \times n$ matrix over a field $\mathbb F.$ If every row of $A_2$ is a linear combination of rows of $A_1,$ prove that $M\big[ \frac{A_1}{A_2}\big] = M[A_1].$

My ideas:

Since every row of $A_2$ is a linear combination of rows of $A_1,$ then we can turn all the rows of $A_2$ to zeros by simple row operation and we are done. Is this a proof to it? If not can someone show me a proof please?

Edit:

Or we have to show that the two matroids have the same rank? But certainly if all the rows were turned into zeros this will happen immediately.

I am just confused what exactly I need to write. Is it a very simple question to answer like this?

Edit

$M[A_1]$ is the matroid corresponding to the matrix $A_1$. And $\frac{A_1}{A_2}$ is the big matrix formed by adding the rows of $A_2$ to the rows of $A_1.$

Edit:

Two matroids are equal if they have the same collection of independent sets or basis, here is a link https://math.stackexchange.com/questions/2211254/how-to-prove-two-matroids-are-equal#:~:text=Since%20a%20matroid%20is%20also,of%20those%20of%20the%20original.&text=It%20is%20necessary%20to%20show%20that%20ground%20sets%20are%20the%20same.

1

There are 1 best solutions below

2
On BEST ANSWER

Apparently, it makes sense to start by clarifying the definition of the matroid $M[A]$, where $A$ is a matrix. The ground set of this matroid consists of the columns of the matrix $A$, the independent sets are linearly independent subsets of the columns of $A$.

Let two matrices $A$ and $B$ have the same number of columns $n\geq1$, $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$ columns of matrices $A$ and $B$ respectively. The equality $M[A]=M[B]$ means that for any $k\leq n$ and any subset $\{i_1,\ldots,i_k\}\subset\{1,\ldots,n\}$ we have $a_{i_1},\ldots,a_{i_k}$ is linearly independent if and only if $b_{i_1},\ldots,b_{i_k}$ is linearly independent. (Strictly speaking, we should not speak about equality but about isomorphism of matroids.)

To prove that $$ M\genfrac{[}{]}{0pt}{}{A_1}{A_2}=M[A_1], $$ where $A_i$ is the matrix given in the question, it is enough to check that if the columns of the matrix $\genfrac{[}{]}{0pt}{}{A_1}{A_2}$ with numbers $i_1,\ldots,i_k$ are linearly independent, then the columns of matrix $A_1$ with the same numbers are linearly independent.

Your considerations about rows are quite suitable for proving this statement.

Edit. Let $a_1,\ldots,a_k$ be columns of matrix $A_1$ with numbers $i_1,\ldots,i_k$ and let $b_1,\ldots,b_k$ be columns of matrix $A_2$ with the same numbers $i_1,\ldots,i_k$. Let $A=(a_1,\ldots,a_k)$ and $B=(b_1,\ldots,b_k)$ be matrices composed of the indicated columns.
Then it follows from the condition that every row of $B$ is a linear combination of rows of $A$ (why?). Now check that if the columns of the matrix $\genfrac{[}{]}{0pt}{}{A}{B}$ are linearly independent, then the columns of matrix $A$ are also linearly independent. To verify this, it is convenient to compare the ranks of matrices $A$ and $\genfrac{[}{]}{0pt}{}{A}{B}$.