Prove or disprove:
Given a square matrix $A$,the columns of $A$ are linearly independent iff. the rows of $A$ are linearly independent.
Asked
Active
Viewed 2.8k times
11
-
i.e. "$\mathbf A$ is singular iff $\mathbf A^\top$ is singular"... – J. M. ain't a mathematician Jul 20 '12 at 07:23
-
Column rank = row rank or $rank(A) = rank(A^T)$ . Read this – sabertooth Jul 20 '12 at 07:26
-
@J.M. Linearly independent rows of $A$ are linearly independent columns of $A^T$, and linearly independent columns of $A^T$ make $A^T$ invertible, which in turn makes $A$ invertible, which finally gives linearly independent columns of $A$. The reverse is also true. Hence, we have proved the problem statement. However, I'm having difficulty accepting/"seeing" the proof intuitively, even though I can logically make the connections. Help! – ryang Jul 20 '12 at 07:37
-
I didn't answer, simply because you haven't mentioned what you're allowed to use. For instance, one (lazy) way of seeing this is that since a matrix and its transpose are similar matrices, then the singularity of one implies the singularity of the other. But that might be too high-powered for the matter at hand... – J. M. ain't a mathematician Jul 20 '12 at 07:50
-
Simplest argument to me is: a square matrix $A$ is invertible $\implies$ $A$ has a right inverse $\implies$ there exists $B$ such that $AB = I$ $\implies$ $B^TA^T = I$ $\implies$ $A^T$ has a left inverse $\implies$ $A^T$ is invertible. Here we use the elementary fact that a square matrix is invertible iff it has a left inverse (the linear map represented by the matrix is injective), iff it has a right inverse (the linear map represented by the matrix is surjective). – Sep 07 '19 at 23:26
2 Answers
12
Here's an argument more-or-less from first principles.
If the rows of $A$ are linearly independent, then the result of doing row-reduction to $A$ is the identity matrix, so the only solution of $Av=0$ is $v=0$.
If the columns of $A$ are linearly dependent, say, $$a_1c_1+a_2c_2+\cdots+a_nc_n=0$$ where the $c_i$ are the columns and the $a_i$ are not all zero, then $Av=0$ where $$v=(a_1,a_2,\dots,a_n)\ne0$$
So, if the columns are dependent, then so are the rows.
Now apply the same argument to the transpose of $A$ to conclude that if the rows of $A$ are dependent then so are the columns.
Gerry Myerson
- 179,216
-
1I understand the proof, but still can't quite believe that columns of a square matrix being LI $\implies$ its rows are LI too. Perhaps I'll get it in the shower some day. – ryang Jul 20 '12 at 22:28
-
If you believe rows of $A$ lin. indep. implies columns of $A$ lin. indep., then you believe rows of $A$-transpose lin. indep. implies columns of $A$-transpose lin. indep. But the rows of $A$-transpose are the columns of $A$, and the columns of $A$-transpose are the rows of $A$. – Gerry Myerson Jul 21 '12 at 05:29
-
-
@Don, I'm sorry to hear that. But if you want someone to help you see how it answers the question, you are going to have to be a lot more forthcoming about just what it is that you don't see. – Gerry Myerson May 10 '15 at 06:10
-
I didn't know about this definition: "If the rows of A are linearly independent, then the result of doing row-reduction to A is the identity matrix, so the only solution of Av=0 is v=0." Where did you read it? – Don Larynx May 10 '15 at 14:32
-
1@Don, it's not a definition, it's a statement of fact. I don't remember where I first read it, but I prove it in lecture every time I teach Linear Algebra. Row operations do not affect linear dependence relations: rows are linearly dependent after row operations if and only if they were linearly dependent before the row operations. The only $n\times n$ matrix in reduced row-echelon form with linearly independent rows is the identity matrix, so if the rows of $A$ are linearly independent then row reduction can only lead to the identity matrix. Continued, next comment. – Gerry Myerson May 10 '15 at 23:39
-
1@Don (continued from last comment), if $I$ is the identity matrix, then the only solution of $Iv=0$ is $v=0$, and row operations have no effect on the solutions to systems, so, if the rows of $A$ are linearly independent, then the only solution of $Av=0$ is $v=0$. – Gerry Myerson May 10 '15 at 23:41
-
-
Yes, didn't realize you meant the zero vector in this line: $$a_1c_1+a_2c_2+\cdots+a_nc_n=0$$ – Don Larynx May 12 '15 at 20:25
-
1I think the proof could be shorter: If the rows of $A$ are linearly independent, then the result of doing row-reduction to $A$ is the identity matrix, so the only solution of $Av=0$ is $v=0$. We have that rows lin. ind. $\implies$ columns lin. independent. Now let's say that columns are independent. Transpose the matrix and apply the same argument. Now we have rows are linearly independent $\iff$ columns linearly independent. And it implies that rows lin. dependent $\iff$ columns lin. dependent. – user4205580 Apr 06 '16 at 16:07
2
A more intuitive argument (why for a square (nxn) matrix ,if it's rows are linearly dependent it implies that so are also it's columns)
Given that rows are linearly dependent,performing Gauss elimination must produce row of all zeroes (possibly more than one) .
Therefore the columns of the row reduced echelon form matrix are linearly dependent. That's so because all have zero in the same entry,thus have only n-1 "free" variables ,non-zero entries ,thus are n-1 dimensional,and n vectors in only n-1 dimensional space- can't be linearly independent.
And since columns of the reduced matrix are linearly depependent , so must be also the columns of the original matrix,which is our claim.
That's so because Gauss elimination preserves relation between columns! More specifically if some column of the original matrix is some linear combination of other columns, then the corresponding columns of the row reduced ,echelon form,matrix mirror this precisely. (otherwise it wouldn't be possible ,for example ,to find null space of the original matrix ,by examining the much simpler columns of it's row reduced echelon form)
serge
- 21