Linear Algebra · Book or PDF

A First Course in Linear Algebra

A.G. Hamilton · Study material generated by AI from this edition. Not affiliated with the publisher.

Chapter 6 · pp. 64–73

Linear Independence and Rank

This chapter asks when a list of vectors contains "redundant" members, meaning vectors that can be built from the others. It shows that the question can be answered with the same Gaussian elimination (GE) process used for simultaneous equations. It then introduces the rank of a matrix and ties rank, independence and invertibility together in one theorem.

Linear combinations

A linear combination of vectors $v_1, v_2, \dots, v_k$ is a sum of numerical multiples of them: $x_1v_1 + x_2v_2 + \dots + x_kv_k$ . The vectors must all be the same size, for example all $3\times 1$ . The multipliers $x_1,\dots,x_k$ can be any numbers, including 0. (p. 64)

Example: $2\begin{bmatrix}1\\0\end{bmatrix}+3\begin{bmatrix}0\\1\end{bmatrix}=\begin{bmatrix}2\\3\end{bmatrix}$ , so $\begin{bmatrix}2\\3\end{bmatrix}$ is a linear combination of the two vectors on the left. (p. 64)

Linear dependence and independence

A list of vectors is linearly dependent (LD) if some non-trivial linear combination of them equals the zero vector. A non-trivial combination has at least one coefficient that is not zero. Choosing every coefficient to be 0 always gives the zero vector, so that choice proves nothing. A list that is not LD is linearly independent (LI). (p. 64)

Example: for $v_1=\begin{bmatrix}1\\2\end{bmatrix}$ and $v_2=\begin{bmatrix}2\\4\end{bmatrix}$ we have $2v_1 - v_2 = 0$ . The coefficients 2 and $-1$ are not all zero, so the list is LD. (p. 64)

Two special cases are worth remembering:

Two non-zero 2-vectors are LD exactly when each is a multiple of the other.
Any list of three 2-vectors is LD. Asking for a combination equal to zero gives 2 equations in 3 unknowns, and such a system must have a non-trivial solution. For instance, $\begin{bmatrix}1\\0\end{bmatrix}$ , $\begin{bmatrix}0\\1\end{bmatrix}$ and $\begin{bmatrix}1\\1\end{bmatrix}$ are LD because the third is the sum of the first two. (p. 64)

Testing for dependence with the GE process

Link to equations. Suppose we want $x_1v_1+\dots+x_qv_q=0$ . Matching entries on the two sides turns this into simultaneous equations whose right-hand sides are all 0. These equations always have the solution $x_1=\dots=x_q=0$ . The list is LD only if there is some other solution. A system has either no solution, one solution, or infinitely many, and it already has one. So another solution exists only if there are infinitely many. In that case GE finishes with a last row of all 0s. (p. 66)

The rule. Let $v_1,\dots,v_q$ be $p$ -vectors.

Make a $p\times q$ matrix $A$ with these vectors as its columns.
Apply the standard GE process to $A$ . The column of zeros on the right-hand side never changes, so it can be left out.
Count the non-zero rows. Fewer than $q$ means the list is LD. Exactly $q$ means it is LI. (pp. 65–66)

Example (LD): put $(1,0,0)$ , $(0,1,0)$ and $(1,1,0)$ in as columns. The matrix $\begin{bmatrix}1&0&1\\0&1&1\\0&0&0\end{bmatrix}$ is already reduced and has only 2 non-zero rows. Since $2<3$ , the list is LD. This agrees with the fact that the third vector is the sum of the first two.

Example (LI): the columns $(1,0,0)$ , $(1,1,0)$ and $(1,1,1)$ give $\begin{bmatrix}1&1&1\\0&1&1\\0&0&1\end{bmatrix},$ which has 3 non-zero rows. The only solution is $x_1=x_2=x_3=0$ , so the list is LI. (pp. 65–66)

Too many vectors. Any list of more than $p$ distinct $p$ -vectors is LD. The matrix has $p$ rows but more than $p$ columns, so after GE it cannot have as many non-zero rows as columns. For example, four 3-vectors can reduce to at most 3 non-zero rows. Four 3-vectors that reduced to rows $(1,1,2,1)$ , $(0,1,1,1)$ , $(0,0,1,-4)$ have 3 non-zero rows, which is fewer than 4, so they are LD. (pp. 66–68)

Rank

The rank of a matrix is the number of non-zero rows left after the standard GE process. For example, a matrix that reduces to rows $(1,2,1)$ , $(0,1,1)$ , $(0,0,0)$ has rank 2. (p. 68)

The rank of a $p\times q$ matrix is at most $p$ and at most $q$ . The reason is that the reduced matrix has 0s everywhere below the main diagonal, which starts at the top left. The most non-zero rows happen when the diagonal has no zeros. Then only the first $q$ rows are non-zero and any remaining rows are all 0s. (p. 68)

Rank also connects to the first rule above: a $p\times q$ matrix has linearly independent columns exactly when its rank equals $q$ . (pp. 66, 68)

Invertibility, rank and independence together

A $p\times p$ matrix is invertible exactly when GE leaves $p$ non-zero rows. This is also the condition for its columns to be LI. So if a square matrix is invertible, its columns form a LI list. (p. 68)

This extends to the Equivalence Theorem. For a $p\times p$ matrix $A$ , the following statements are equivalent, meaning all true or all false:

$A$ is invertible.
The rank of $A$ is $p$ .
The columns of $A$ are LI.
The equations $Ax=0$ have only the solution $x=0$ .

The reason is that in each case GE leaves $p$ non-zero rows. (p. 70)

Examples of how this works:

When $A=\begin{bmatrix}1&2&3\\1&1&2\\1&-1&1\end{bmatrix}$ , GE gives rows $(1,2,3)$ , $(0,1,1)$ , $(0,0,1)$ . That is 3 non-zero rows, so the rank is 3, the columns are LI, and $A$ is invertible. (p. 69)
For a $3\times 3$ matrix whose GE result has rows $(1,3,-1)$ , $(0,1,-1)$ , $(0,0,0)$ , the rank is 2. The columns are LD, the inverse-finding process fails, and $Ax=0$ has infinitely many solutions. All four conditions fail together. (p. 69)

A common misconception

Some students think a square matrix is invertible as long as no column is entirely zero. That is wrong. Invertibility depends on how many non-zero rows GE leaves, not on whether entries are zero. The matrix in the second example above has no zero column, yet its rank is 2, not 3, so it is not invertible. (pp. 68–70)

Another mistake is to think rank can be larger than the number of rows or columns. It cannot: a $p\times q$ matrix has rank at most the smaller of $p$ and $q$ . (p. 68)

Check yourself

Write down a non-trivial linear combination of $\begin{bmatrix}1\\3\end{bmatrix}$ and $\begin{bmatrix}2\\6\end{bmatrix}$ that equals the zero vector. What does this tell you about the list?
Why is a list of five 4-vectors always linearly dependent?
Describe how to test three 3-vectors for independence using GE. What result tells you the list is LI?
A $4\times 4$ matrix has rank 3. Is it invertible? Are its columns LI? Does $Ax=0$ have non-zero solutions?
Explain why a $3\times 5$ matrix cannot have rank 4.