# Linear independence of row vectors

I am following Gelfand's "Lectures on Linear Algebra". On the 4th page there is given a definition of a vector space being n-dimensional:

A vector space R is said to be n-dimensional if it contains $n$ linearly independent vectors and if any n+1 vectors in R are linearly dependent.

After that the author wants to show that $n$-tuples of real numbers make an $n$-dimensional vector space.

This space contains $n$ linearly independent vectors. For instance, the vectors

$x_1 = (1, 0, 0, ..., 0)$

$x_2 = (0, 1, 0, ..., 0)$

...

$x_n = (0, 0, 0, ..., 1)$

are easily seen to be linearly independent. On the other hand, any $m$ vectors, $m>n$, are linearly dependent. Indeed, let

$y_1 = (z_{11}, z_{12}, ... z_{1n})$

$y_2 = (z_{21}, z_{22}, ... z_{2n})$

...

$y_m = (z_{m1}, z_{m2}, ... z_{mn})$

be $m$ vectors, $m > n$. The number of linearly independent rows in the matrix

$z_{11}, z_{12}, ... z_{1n}$

$z_{21}, z_{22}, ... z_{2n}$

...

$z_{m1}, z_{m2}, ... z_{mn}$

cannot exceed $n$ (the number of columns). Since $m > n$, our $m$ rows are linearly dependent. But this implies the linear dependence of the vectors $y_1, y_2, ..., y_m$.

Thus the dimension of R is $n$.

I have an issue with the line "the number of linearly independent rows in the matrix cannot exceed the number of columns". The book treats this statement as an obvious one, but for me it looks like a tautology. I understand the rest of the argument though.

My question is how to prove this statement rigorously, using only basic definitions of linear independence and $n$-dimensionality given in the textbook.

P.S.: sorry for poor formatting, I am a newbie to LaTeX.

• Do you know how to identify if rows are linearly independent using a matrix? The common technique taught is to perform row reduction and Gaussian Elimination. The result of such row reduction would be a matrix with pivot points. Note that there can be at most one pivot point per row as well as at most one pivot point per column. It follows trivially then that for an $m\times n$ matrix $A$ one has the number of pivots of $A$ is bounded by $rank(A)\leq \min\{m,n\}$ – JMoravitz Sep 7 '18 at 15:10
• I agree that the key lies in Gaussian elimination algorithm. – Giuseppe Negro Sep 7 '18 at 15:27
• Does he really use $\mathbb R$ for a general vector space? – Bungo Sep 7 '18 at 15:45
• @Bungo, that was someone's edit. I have fixed that, thank you for pointing out. The author of the original text had used R (bold R), and I have copied the text in the original form. – George Pak Sep 9 '18 at 7:36
• @JMoravitz, I was in doubt if row reduction can serve as the rigorous prove of the statement, but if you say so - I believe it now, thank you – George Pak Sep 9 '18 at 7:38

Let $p(n)$ be the statement "Any $n+1$ rows of $n$-tuples are linearly dependent."

$p(1)$ is straight forward to prove.

I will show $p(n) \rightarrow p(n+1)$.

Fix $n+2$ rows of $(n+1)$-tuples. Name the rows $X_1, … , X_{n+2}$

If we strike the last column and last row, we will have $n+1$ rows of $n$ tuples and then we can use $p(n)$ to get a linear combination $a_1 \hat X_1 + … + a_{n+1} \hat X_{n+1} = 0$ where $a_i$ not all $0$, and the hats mean that the last entry has been truncated from each tuple.

$Y = a_1 X_1 + … + a_{n+1} X_{n+1}$ is a row of all zeros, except for possibly the last entry. If the last entry of $Y =0$, then the sequence of coefficients $(a_1, …, a_{n+1}, 0)$ is a witness to the linear dependence of $X_1, …, X_{n+2}$ and we are done.

Or else divide $Y$ by its last entry to get a tuple $(0, 0,…, 0, 1)$. You can see that if we chose to strike a different column, we could have chosen the $1$ to appear in any entry. But now we are also done because these $Y$'s that we have created can be used to create a linear dependence with the last $(n+2)^{th}$ row.

• Note this proof can be interpreted as a recursive algorithm to construct the coefficients that witness linear dependence of the vectors. However, it's a lot less efficient than row reduction. – Mark Sep 9 '18 at 9:30