Show that no row of $A$ contains exactly one non-zero entry.

Question

Here is the question I am trying to tackle:

Let $A$ be a non-zero matrix over a field $\mathbb F$ and suppose that $M[A]$ has no coloops. Show that no row of $A$ contains exactly one non-zero entry.

My thoughts:

Will this matrix necessarily be in a row echelon form? And we will arrive to a contraction from here?

I know the following about coloops:

A loop of $M^*$ is called a coloop of $M.$ An element $f$ is a coloop if it belongs to every basis.

Also, an element $f$ in the ground set $E$ of a matroid $M$ is a coloop if any of the following equivalent conditions hold:

1- If $I$ is an independent set, then $I \cup f$ is an independent set.

2- $rk_M(E\setminus f) = rk(M) - 1.$

3- $E\setminus f$ is flat.

Still, I can not combine these ideas to come up with a neat and clean solution. Could someone help me please?

Answer 1

It is easier to consider the converse -- where we have a column $u$ which has exactly one non-zero entry, and we show it is a coloop.

The matrix $A$ does not necessarily have to in row echelon form, but you can convert it into row echelon form without changing the induced matroid. Assuming $A$ has $n$ columns, we define $M[A]$ to be the matroid on $[n] = \{1, 2, \dots n\}$ with a set $S \subseteq [n]$ being independent if one of the two (definitionally) equivalent conditions is true:

1. the set $\{ A e_{i} : i \in S \}$ of columns of $A$ corresponding to $S$ are linearly independent, or
2. the only $v \in \mathrm{Span}\{ e_{i} : i \in S \}$ with $Av = 0$ is $v=0$.

To be clear, since $Av$ represents a linear combination of the columns of $A$ with coefficients $v_{i}$, if $Av = 0$ for nonzero $v \in \mathrm{Span}\{ e_{i} : i \in S \}$ that is saying there is a nontrivial linear combination of the columns indexed by $S$ which is zero (ie the condition for linear dependence).

The first is what usually gets stated, but I mention the more direct second condition since for any invertible matrix $R$, condition (2) is unchanged by left multiplying by $R$. When $R$ is an elementary matrix, this multiplication represents a row operation.

Thus we can assume $A$ is in row echelon form. This makes it easier to think about the column with only a single nonzero entry. If $u = \lambda e_{j}$ is the column in question ($\lambda$ an arbitrary scalar, and $e_{j}$ the $j$th standard basis vector), then necessarily every other column in $A$ must have a zero in the $j$ entry. So $A$ is of the form $$ A = \begin{pmatrix} B_{1} \ &0 \ &B_{2} \\ 0 \ &\lambda \ &0 \\ B_{3} \ &0 \ &B_{4} \end{pmatrix}. $$ where the $B_{i}$ are block matrices of appropriate size. In other words, the other columns span a space that our $u = \lambda e_{j}$ does not live in. Thus $u$ must be a coloop -- throwing it into any subset of the other columns must increase the rank.

If this argument isn't clear, then consider the case where your field is $\mathbb{R}$, $A$ is $n \times n$, and $u = \lambda e_{n}$. The general case is essentially equivalent to this special case (well really the $n \times m$ matrix version of this).

Answer 2

The key is the definition of $M[A]$. By definition, a subset of $E$ is an independent set of $M[A]$ if and only if the corresponding columns are linearly independent.

Assume that $A$ has a row with exactly one non-zero entry, say it is in the first column. Then, the first column of $A$ cannot be written as a combination of all the other columns. Hence the first element in the ground set $E$ belongs to every basis or, in other words, it is a coloop.