Simple proof linearly dependent column imply linearly dependent rows

Question

I am wondering if there is an easy/simple way to show that if for a given a matrix $A$ there is a non-zero vector $x$ such that $Ax=0$ then there is a non-zero vector $y$ such that $y^TA=0$ What I am after here is whether there is some way to go more or less directly from the fact that given that such an $x$ exists there is a $y^T$ that will provide the linear combination of rows which results in a zero vector. In particular can we do it without already knowing that the span of the column space and row space are equal?

Answer 1

I assume you want $A$ to be an $n \times n$ square matrix, otherwise the $1 \times 2$ matrix $A = \begin{bmatrix}1 & 1\end{bmatrix}$ is a counterexample.

(Side observation. The span of the columns need not be equal to the span of the rows - what you mean is that they have the same dimension.)

Assume there is is a non-zero $x$ such that $A x = 0$. We can assume WLOG that the first column of $A$ is a linear combination of the others, or more precisely $$ x = \begin{bmatrix} -1\\ z \end{bmatrix}, $$ where $z$ is a column vector of length $n-1$.

If $B$ is the $n \times (n-1)$ matrix obtained removing the first column from $A$, then $$\tag{prod} A = B Z, $$ where $Z$ is the $(n-1) \times n$ block matrix $$ Z = \begin{bmatrix} z & | &I \end{bmatrix}, $$ where $I$ is the identity $(n-1) \times (n-1)$ matrix.

Now (prod) shows the $n$ rows of $A$ are linear combinations of the rows of $Z$. Since $Z$ has $n - 1$ rows, this means that the rows of $A$ are linearly dependent, that is, there is a $y \ne 0$ such that $y^{t} A = 0$.

I am aware of the fact that you might consider this argument not to be satisfactory, because it reproduces part of the proof that the row rank equals the column rank.