6. Rank and Linear Independence

1. Rank

The rank of matrix in the number of pivots ($r(A) = \# $ of pivots)

• Also defiend as the maximum number of linearly independent columns (will be discussed later)

 

The rank of a matrix gives in a sense the true size of the matrix. Consider an $(m \times n)$ matrix $A$ whose rank is few than $m$. While $A \mathbf{x} = \mathbf{0}$ seems to have $m$ linear equations, $m-r$ out of $m$ equations are redundant in the sense that they can be derived from the rest of the equations.

 

From now on, consider $(m \times n)$ size matrix $A$.

Note : $r(A) \leq \min \{m, n\}$ (why? each column and row can have at most one pivot)

 

 

2. Full column Rank

full column rank : matrix $A$ whose $r(A) = n$

• $n$ pivot columns
• no free variables
• $N(A) = \{ \mathbf{0} \}$ ($N(A)$는 free variable의 선형 결합으로 표현되는데 free variable이 없으므로)
• $A \mathbf{x} = \mathbf{b}$ has $0$ or $1$ number of solution ($\mathbf{b}$가 column vector들의 span에 있는지 여부에 따름)

 

 

3. Full row Rank

full row rank : matrix $A$ whose $r(A) = m$

• $A \mathbf{x} = \mathbf{b}$ always solvable (see below)

• $C(A) = \mathbb{R}^{m}$ ($\mathbf{b} \in \mathbb{R}^{m}$인 어떤 $\mathbf{b}$에 대해서라도 $A \mathbf{x} = \mathbf{b}$가 solvable 하므로,  $\mathbf{b} \in C(A)$라는 뜻이다. 그러려면 $C(A) = \mathbb{R}^{m}$ 이다.
• $n-m$ special solution(s)

 

 

4. $r(A)$ and Number of Solutions to $A \mathbf{x} = \mathbf{b}$

$r(A)$	Number of solutions
$r(A) = m \ \& \ r(A) = n$	$1$ sol ($A$ : square and invertible)
$r(A) = m \ \& \ r(A) < n$ (full row rank)	$\infty$ solutions ($n-r$ special solutions)
$r(A) < m \ \& \ r(A) = n$ (full column rank)	$0$ or $1$ solution (no special solutions, $N(A) = \{\mathbf{0} \}$)
$r(A) < m \ \& \ r(A) < n$	$0$ or $\infty$ solutions ($x_{p}$(particular solution)의 존재 여부에 따름)

 

 

 

5. Linear Independence

Vectors $\mathbf{v_{1}}, \mathbf{v_{1}}, ..., \mathbf{v_{n}}$ are said to be linearly independent if their linear combination $x_{1} \mathbf{v_{1}} + x_{2} \mathbf{v_{2}} + ... + x_{n} \mathbf{v_{n}} = \mathbf{0}$ only when $x_{i} = 0, \ \forall i$. Vectors that are not linearly independent are linearly dependent

 

Interpretation

• dependent 하다면 어떤 한 벡터는 나머지 다른 벡터들의 선형 결합으로 표현된다.

 

Rank and Independence

• Indeed, $r(A)$ is also defined as the maximum number of linearly independent columns in $A$
• It can be shown that row rank is equal to column rank for any matrix
• So, $r(A) = r(A^{T}) = \# $ of maximum linearly independent columns (rows)

 

 

6. Checking Linear Independence

Fact : Any set of $n$ vectors in $\mathbb{R}^{m}$ must be linearly dependent if $n > m$

(그 벡터들을 column으로 하는 행렬 $A$를 만들었을 때, $r(A)$의 최댓값이 $m$이기 때문이다. 이 말은 linearly independent한 column vector의 개수가 $m$이라는 뜻이므로 $n-m$개의 나머지 벡터들은 linearly dependent 할 수 밖에 없다)

 

How to check whether set of vectors are linearly independent or not?

 

Given : $\mathbf{v_{1}}, \mathbf{v_{1}}, ..., \mathbf{v_{n}} \in \mathbb{R}^{m}$

• If $n > m$, then dependent
• Else
  1. Construct a matrix $A = [\mathbf{v_{1}}, \mathbf{v_{1}}, ..., \mathbf{v_{n}} ]$
  2. Apply GE to $A$, and compute $r(A)$
  3. If $r(A) = n$, then independent. Ohterwise, dependent