Rank and linear independence
Rank and Linear Independence
Rank and linear independence tell us whether vectors or equations contain genuinely new information.
They are essential for understanding:
- linear systems
- redundant constraints
- basis matrices
- basic feasible solutions
- simplex pivots
Linear Dependence
Vectors:
\[v_1,v_2,\ldots,v_m\]are linearly dependent if there exist scalars:
\[\alpha_1,\alpha_2,\ldots,\alpha_m\]not all zero, such that:
\[\alpha_1v_1+\alpha_2v_2+\cdots+\alpha_mv_m=0\]This means at least one vector can be written as a linear combination of the others.
Linear Independence
Vectors:
\[v_1,v_2,\ldots,v_m\]are linearly independent if:
\[\alpha_1v_1+\alpha_2v_2+\cdots+\alpha_mv_m=0\]only when:
\[\alpha_1=\alpha_2=\cdots=\alpha_m=0\]This means none of the vectors is redundant.
Simple Example
The vectors:
\[v_1=(1,0), \qquad v_2=(0,1)\]are linearly independent.
If:
\[\alpha_1(1,0)+\alpha_2(0,1)=(0,0)\]then:
\[(\alpha_1,\alpha_2)=(0,0)\]so:
\[\alpha_1=0,\qquad \alpha_2=0\]Dependent Example
The vectors:
\[v_1=(1,2), \qquad v_2=(2,4)\]are linearly dependent because:
\[v_2=2v_1\]So $v_2$ adds no new direction.
Zero Vector Rule
Any set of vectors containing the zero vector is linearly dependent.
Example:
\[\{(1,0), (0,0)\}\]is dependent because:
\[0(1,0)+1(0,0)=(0,0)\]with coefficients not all zero.
Standard Unit Vectors
The standard unit vectors:
\[e_1,e_2,\ldots,e_n\]are linearly independent.
They form the canonical basis of $\mathbb{R}^n$.
Maximum Number of Independent Vectors
In $\mathbb{R}^n$, a linearly independent collection can have at most $n$ vectors.
For example:
- in $\mathbb{R}^2$, at most 2 independent vectors
- in $\mathbb{R}^3$, at most 3 independent vectors
- in $\mathbb{R}^n$, at most $n$ independent vectors
Rank
The rank of a matrix is the number of linearly independent rows or columns.
For a matrix $A$:
\[\operatorname{rank}(A)\]is the dimension of the space spanned by its columns.
Equivalently, it is also the dimension of the space spanned by its rows.
Column Rank
The column rank is the number of linearly independent columns of $A$.
If:
\[A = [A_1 \ A_2 \ \cdots \ A_n]\]then the column rank tells us how many of these columns carry independent information.
Row Rank
The row rank is the number of linearly independent rows of $A$.
A crucial theorem says:
\[\text{row rank} = \text{column rank}\]So we simply say the rank.
Full Row Rank
If:
\[A \in \mathbb{R}^{m\times n}\]then $A$ has full row rank if:
\[\operatorname{rank}(A)=m\]This means all rows are independent.
In standard-form LP, we often assume $A$ has full row rank:
\[\operatorname{rank}(A)=m\]This means there are no redundant equality constraints.
Full Column Rank
If:
\[A \in \mathbb{R}^{m\times n}\]then $A$ has full column rank if:
\[\operatorname{rank}(A)=n\]This means all columns are independent.
Rank and Linear Systems
For a system:
\[Ax=b\]the augmented matrix is:
\[[A|b]\]The system has at least one solution if and only if:
\[\operatorname{rank}(A)=\operatorname{rank}([A|b])\]If:
\[\operatorname{rank}(A)<\operatorname{rank}([A|b])\]then the system is inconsistent.
Rank in Standard Form LP
A standard-form LP is:
\[\min c^Tx\]subject to:
\[Ax=b\] \[x\ge 0\]where:
\[A\in\mathbb{R}^{m\times n}\]Common assumptions:
\[\operatorname{rank}(A)=m\]and:
\[m<n\]The first assumption means no redundant equations.
The second means there are more variables than equality constraints, so the feasible set may contain many candidate solutions.
Redundant Constraints
If:
\[\operatorname{rank}(A)<m\]then some equality constraints are linearly dependent on the others.
This means some equations are redundant and could be removed.
Example:
\[x_1+x_2=5\] \[2x_1+2x_2=10\]The second equation is just twice the first.
Rank and Basis Matrices
In standard-form LP, a basis matrix $B$ is formed by selecting $m$ columns of $A$.
For $B$ to be a valid basis matrix, its columns must be linearly independent.
That means:
\[\operatorname{rank}(B)=m\]Since $B$ is $m\times m$, this also means $B$ is invertible.
Why Independence Matters in Simplex
Simplex works by moving from one basis to another.
Each basis must be made of independent columns.
If the chosen columns are dependent, then:
\[B^{-1}\]does not exist, so we cannot compute:
\[x_B = B^{-1}b\]Therefore, no valid basic solution is produced.
Unique Coordinates
If vectors are linearly independent, then any vector written as their linear combination has unique coefficients.
This matters because if:
\[B = [A_{B(1)} \ \cdots \ A_{B(m)}]\]is a basis matrix, then:
\[x_B = B^{-1}b\]is uniquely determined.
Quick Test for Two Vectors in $\mathbb{R}^2$
Two nonzero vectors in $\mathbb{R}^2$ are dependent if one is a scalar multiple of the other.
Example:
\[(2,4)\]and:
\[(1,2)\]are dependent because:
\[(2,4)=2(1,2)\]But:
\[(1,0)\]and:
\[(0,1)\]are independent.
Quick Test for Square Matrices
For a square matrix $B$:
\[B \text{ is invertible}\]if and only if:
\[\operatorname{rank}(B)=m\]where $B$ is $m\times m$.
Equivalently, its columns are linearly independent.
OR Interpretation
Rank and independence answer questions like:
- Are these constraints redundant?
- Can this system be solved?
- Does this selected basis define a valid basic solution?
- Can we invert the basis matrix?
- Are the active constraints enough to define a vertex?
Checklist
You understand rank and independence if you can:
- define linear dependence
- define linear independence
- detect scalar multiples
- explain why zero vectors cause dependence
- define rank
- explain full row rank
- use rank to discuss consistency of $Ax=b$
- explain why a basis matrix must have independent columns
- connect invertibility with rank
See Also
- Vectors
- Matrices
- Linear Combinations
- Linear Systems
- Bases and Invertible Matrices
- Basic Feasible Solutions
- Simplex Method
Exam checkpoint
Use this topic only as much as needed to support LP algebra: matrices, rank, bases, linear systems, half-spaces, and hyperplanes. Connect every computation back to $Ax=b$, basis matrices, and feasible regions.