Rank of a homogenous system of linear equations

Dependencies:

  1. System of linear equations
  2. Rank of a matrix
  3. RREF is unique
  4. Equations with row equivalent matrices have the same solution set
  5. Basis of a vector space

Let $AX = 0$ be a system of $m$ linear equations in $n$ variables. Then $\operatorname{rank}(A) = n \iff$ the only solution is $X = 0$. If $\operatorname{rank}(A) < n$, then $AX = 0$ has infinitely many solutions. ($\operatorname{rank}(A) > n$ is not possible.) Also, $\dim(\{x: Ax = 0\}) = n - \operatorname{rank}(A)$.

Proof

Let $R = \operatorname{RREF}(A)$. Then $R$ is row equivalent to $A$. Therefore, $[R|0]$ is row equivalent to $[A|0]$. Therefore, $RX = 0$ has the same solution set as $AX = 0$.

Define the $i^{\textrm{th}}$ pivot $\alpha_i$ to be the smallest $j$ for which $R[i, j]$ is non-zero, where $0 \le i \le \operatorname{rank}(A)$. Since $R$ is in RREF, $\alpha_i < \alpha_{i+1}$ and \[ R[k, \alpha_i] = \begin{cases}0 & k \neq i \\ 1 & k = i \end{cases} \]

Let $P$ be the set of pivots and $Q$ be the column indices which are not pivots. $|P| = \operatorname{rank}(A)$ and $|Q| = n - \operatorname{rank}(A)$. For $j \in P$, let us define $X_j$ to be a pivot variable and for $j \in Q$, $X_j$ to be a non-pivot variable. This definition is sound because $P$ and $Q$ have elements in the range 1 to $n$ and $X$ is an $n$ by $1$ matrix.

Consider the $i^{\textrm{th}}$ equation in $RX = 0$:

\begin{align} 0 &= (RX)[i, 1] \\ &= \sum_{j=1}^m R[i, j]X[j, 1] \\ &= \sum_{\alpha_k \in P} R[i, \alpha_k] X[\alpha_k, 1] + \sum_{j \in Q} R[i, j] X[j, 1] \\ &= \sum_{\alpha_k \in P} \begin{Bmatrix} 0 & i \neq k \\ 1 & i = k \end{Bmatrix} X[\alpha_k, 1] + \sum_{j \in Q} R[i, j] X[j, 1] \\ &= X[\alpha_i, 1] + \sum_{j \in Q} R[i, j] X[j, 1] \\ &\iff X[\alpha_i, 1] = - \sum_{j \in Q} R[i, j] X[j, 1] \end{align}

Therefore, by fixing arbitrary values for non-pivot variables, we can find a unique value of the $i^{\textrm{th}}$ pivot variable which satisfies the $i^{\textrm{th}}$ equation.

If $z$ is a non-zero solution to $AX = 0$, then $\beta z$ is also a solution to $AX = 0$ for any $\beta \in \mathbb{R}$. Hence, if $AX = 0$ has a non-zero solution, then there are an infinite number of solutions.

If $\operatorname{rank}(A) < n$, then $Q \neq \{\}$. Therefore, a non-zero solution exists because non-pivot variables can take on non-zero values.

If $\operatorname{rank}(A) = n$, every column is a pivot column, so $Q = \{\}$. \[ X[\alpha_i, 1] = - \sum_{j \in Q} R[i, j] X[j, 1] = 0 \] Therefore, $X = 0$.

Let $z^{(i)}$ be a solution to $AX = 0$ where the $i^{\textrm{th}}$ non-pivot variable is 1 and the other non-pivot variables are 0. Then any solution to $AX = 0$ can be written as a linear combination of $\{z^{(i)}: 1 \le i \le |Q|\}$. Furthermore, $\{z^{(i)}: 1 \le i \le |Q|\}$ is linearly independent. Hence, it is a basis of $\{x: Ax = 0\}$, and so $\dim(\{x: Ax = 0\}) = |Q| = n - \operatorname{rank}(A)$.

Dependency for:

  1. Extreme point iff BFS
  2. Bounded section of pointed cone
  3. Condition for existence of BFS in a polyhedron
  4. Dimension of a polyhedron
  5. Pointing a polyhedron
  6. Point in polytope is convex combination of BFS
  7. BFS is vertex
  8. Every complex matrix has an eigenvalue
  9. Characteristic polynomial of a matrix
  10. Full-rank square matrix is invertible
  11. AB = I implies BA = I
  12. Homogeneous linear equations with more variables than equations

Info:

Transitive dependencies:

  1. /linear-algebra/vector-spaces/condition-for-subspace
  2. /linear-algebra/matrices/gauss-jordan-algo
  3. /sets-and-relations/equivalence-relation
  4. Group
  5. Ring
  6. Polynomial
  7. Integral Domain
  8. Comparing coefficients of a polynomial with disjoint variables
  9. Field
  10. Vector Space
  11. Linear independence
  12. Span
  13. Semiring
  14. Matrix
  15. Stacking
  16. System of linear equations
  17. Product of stacked matrices
  18. Matrix multiplication is associative
  19. Reduced Row Echelon Form (RREF)
  20. Matrices over a field form a vector space
  21. Row space
  22. Elementary row operation
  23. Every elementary row operation has a unique inverse
  24. Row equivalence of matrices
  25. Row equivalent matrices have the same row space
  26. RREF is unique
  27. Identity matrix
  28. Inverse of a matrix
  29. Inverse of product
  30. Elementary row operation is matrix pre-multiplication
  31. Row equivalence matrix
  32. Equations with row equivalent matrices have the same solution set
  33. Rank of a matrix
  34. Basis of a vector space
  35. Linearly independent set is not bigger than a span
  36. Homogeneous linear equations with more variables than equations