Linear Independence, Rank, and Bases

Given a handful of vectors, is any one of them redundant? The answer decides whether they can serve as a basis, and a basis is what every later method is built on.

This sits beneath the linear programming units rather than after them. A basic feasible solution is defined by a set of linearly independent columns, and every simplex iteration solves a system against the basis matrix, which works only because that matrix is invertible. Both facts are used constantly; this unit is where they are established.

The unit is also where a common shortcut gets corrected. Checking that no two vectors are parallel feels like checking independence, and it is not the same test.

This unit assumes you can multiply a matrix by a vector and solve a two-by-two system.

Given a collection of vectors, ask: can any one of them be built out of the others? If yes, that vector contributes no direction the rest do not already reach, and dropping it loses nothing. The set is dependent.

If no vector can be built from the others, every one of them adds something genuinely new, and the set is independent.

Rank counts what survives this pruning: how many genuinely different directions the columns supply between them.

Invertibility is the case where a square matrix's columns supply exactly as many directions as the space has dimensions. Then every target can be reached, and reached in exactly one way, which is why $Ax=b$ has a unique solution precisely when $A$ is invertible.

The difficulty is that "builds out of the others" means combining several vectors, not only scaling one. Two vectors can fail to be multiples of each other while a third is still reachable from the pair. That is why a pairwise check is not an independence check, and it is the point of the contrast case later in this unit.

Linear combination. For vectors $v_1,\dots ,v_k$ and scalars ${\lambda }_1,\dots ,{\lambda }_k$, the vector ${\lambda }_1{v}_1+\cdots +{\lambda }_k{v}_k$ is a linear combination of them.

Linear independence. The vectors are linearly independent when

forces ${\lambda }_1=\cdots ={\lambda }_k=0$. If any solution has some ${\lambda }_i\ne 0$, the set is dependent, and that equation can be rearranged to express $v_i$ in terms of the others.

Note what the definition quantifies over: all scalars at once, not pairs.

Rank. The rank of a matrix $A$ is the size of its largest independent set of columns. It equals the number of pivots in the reduced row echelon form of $A$, and equals the corresponding count for the rows: column rank and row rank always agree.

Invertibility. For a square $A\in {\mathbb{R}}^{m\times m}$ the following say the same thing:

1. the columns of $A$ are linearly independent;
2. $\mathrm{rank}(A)=m$;
3. $detA\ne 0$;
4. $A^{-1}$ exists;
5. $Ax=b$ has exactly one solution for every $b$.

A set of columns can serve as a basis exactly when it satisfies these, which is why the basis matrix in a linear program must have independent columns.

Independent. Take

Suppose ${\lambda }_1{a}_1+{\lambda }_2{a}_2=0$. Reading the two rows gives ${\lambda }_1+3{\lambda }_2=0$ and $2{\lambda }_1+{\lambda }_2=0$. From the second, ${\lambda }_2=-2{\lambda }_1$; substituting into the first gives ${\lambda }_1-6{\lambda }_1=-5{\lambda }_1=0$, so ${\lambda }_1=0$ and then ${\lambda }_2=0$. Only the trivial combination vanishes, so the pair is independent.

Equivalently, the matrix has determinant $1-6=-5\ne 0$.

Dependent. Now add

Three vectors in ${\mathbb{R}}^2$ are always dependent, because rank cannot exceed 2. The counting argument settles the question before any computation.

The explicit relation is

since $-1+3=2$ in the first component and $-2+1=-1$ in the second. Rearranged, $a_1-a_2+a_3=0$ is a nontrivial combination giving the zero vector.

What this shows. No two of $a_1,a_2,a_3$ are multiples of one another, yet the set is dependent. Independence is not a pairwise property.

Count first. If there are more vectors than components, they are dependent and no computation is needed: $k$ vectors in ${\mathbb{R}}^m$ with cannot be independent. If any vector is the zero vector, the set is dependent for the same trivial reason.

For two vectors, check proportionality. A pair is dependent exactly when one is a scalar multiple of the other. This shortcut is valid for two vectors only, and using it on three or more is the error this unit warns about.

For a square set, use the determinant. Form the matrix whose columns are the vectors. A nonzero determinant means independent; zero means dependent. This answers the question but does not show the relationship.

Otherwise reduce. Put the vectors in as columns and row reduce. The number of pivots is the rank. If the rank equals the number of vectors, they are independent; if it is smaller, they are dependent.

If dependent, exhibit the relation. A column without a pivot is a combination of the pivot columns, and the reduced form's entries are the coefficients. Solve for them explicitly rather than stopping at "dependent".

Verify the relation. Substitute the coefficients back and check every component. A dependence claim with arithmetic behind it is checkable; one without is an assertion.

For a square matrix, name the consequence. Independent columns mean the matrix is invertible, $Ax=b$ has exactly one solution for every $b$, and the columns can serve as a basis. Dependent columns mean none of those hold.

Problem. Decide whether

has independent columns. If it does, find $B^{-1}$ and solve $Bx=\left(\begin{array}{c}12\\ 12\end{array}\right)$.

Goal. Establish independence, then use it.

Relevant principle. For a square matrix, independent columns, nonzero determinant, and invertibility are the same condition.

Step 1: count. Two vectors in ${\mathbb{R}}^2$, so the counting argument does not settle it. Continue.

Step 2: check proportionality. Is $(1,2{)}^{\mathsf{T}}$ a multiple of $(2,1{)}^{\mathsf{T}}$? Scaling the first component by $1/2$ would give $(1,1/2{)}^{\mathsf{T}}$, not $(1,2{)}^{\mathsf{T}}$. They are not proportional.
Reason: with exactly two vectors, proportionality is a valid test, and it already answers the question.

Step 3: confirm with the determinant.

so the columns are independent and $B$ is invertible.

Step 4: form the inverse. For the inverse is , giving

Check: , as required.

Step 5: solve the system.

Check. $2(4)+4=12$ and $4+2(4)=12$. Both rows hold.

Interpretation. Because the columns are independent, this is the only solution. Had they been dependent, the system would have had either no solution or infinitely many, and no inverse would exist to pick one out.

This matrix is not arbitrary: it is the basis matrix reached at the end of the simplex worked example, where the same system gives the optimal $x_1=x_2=4$. The independence established here is what made that final step well defined.

Checking that no two vectors are multiples of each other is a valid test for a set of two. Applied to three or more it gives the wrong answer, and it gives it confidently.

The tempting reasoning. Take

No two are proportional: $a_2$ is not a multiple of $a_1$, nor $a_3$ of $a_1$, nor $a_3$ of $a_2$. Each points a different way. So the set looks independent.

Why it is not. The definition allows all three coefficients to vary at once, and

is a nontrivial combination giving zero. Equivalently $a_3=-a_1+a_2$: the third vector is reachable from the first two, so it adds no new direction.

The counting argument settles it instantly. Three vectors in ${\mathbb{R}}^2$ are always dependent, whatever they look like, because rank cannot exceed the number of components. The pairwise check cannot see this, since it never considers three vectors together.

Where it does real damage. In a linear program, a basis is a set of $m$ columns that must be independent. Selecting columns by eye because they look different produces a singular basis matrix, and then $A_B^{-1}$ does not exist: the basic solution is undefined and the iteration cannot proceed. The failure appears as a division by zero deep in the arithmetic rather than as a clear message about the columns.

The reliable test. Count first; if the count does not settle it, reduce or take a determinant. Reserve the proportionality check for pairs.