Rank, column space, null space — AI-ML notes

WHAT are these objects?

WHY this equals a span: $Ax = x_1a_1 + x_2a_2 + \dots + x_na_n$ . So any output is just a linear combination of the columns. Choosing $x$ = choosing weights. Hence the reachable outputs are exactly the span of the columns.

HOW to compute them (derivation via elimination)

Procedure:

Row-reduce $A$ to RREF $R$ . Pivot columns = positions of leading 1's.
$\text{rank} =$ number of pivots.
$\text{Col}(A) =$ span of the pivot columns of the original $A$ (not of $R$ !).
$\text{Null}(A)$ : assign each free variable a parameter, back-substitute to get special solutions; they form a basis.

The Rank–Nullity Theorem (derived, not memorized)

Derivation from scratch. Row-reduce $A$ (with $n$ columns). Every column is either a pivot column or a free column.

Number of pivot columns $= \text{rank}(A)$ .
Each free column gives exactly one free variable, and each free variable produces exactly one special solution — a basis vector of $\text{Null}(A)$ . These special solutions are independent (each has a lone $1$ in its own free slot).
So $\dim(\text{Null}(A)) =$ number of free columns.

Since every column is pivot or free, exactly once: $\underbrace{(\#\text{pivots})}_{\text{rank}} + \underbrace{(\#\text{free})}_{\dim\text{Null}} = \underbrace{n}_{\text{total columns}}. \qquad\blacksquare$

Worked examples

Worked example Example 1 — full pipeline

$A=\begin{bmatrix}1&2&1\\2&4&3\\3&6&4\end{bmatrix}$ Row reduce. $R_2\!\to\!R_2-2R_1$ , $R_3\!\to\!R_3-3R_1$ : $\begin{bmatrix}1&2&1\\0&0&1\\0&0&1\end{bmatrix}\xrightarrow{R_3-R_2}\begin{bmatrix}1&2&1\\0&0&1\\0&0&0\end{bmatrix}\xrightarrow{R_1-R_3}\begin{bmatrix}1&2&0\\0&0&1\\0&0&0\end{bmatrix}=R.$ Why this step? We clear below then above pivots to reach RREF, exposing pivot columns 1 and 3.

rank $=2$ (two pivots).
Col(A) = span of columns 1 and 3 of original $A$ : $\text{span}\{(1,2,3)^T,(1,3,4)^T\}$ . Why? Column 2 $= 2\times$ column 1 (dependent), so it adds no reach.
Null(A): free variable $x_2=t$ . From $R$ : $x_1+2x_2=0\Rightarrow x_1=-2t$ ; $x_3=0$ . Special solution $x=t(-2,1,0)^T$ . So $\text{Null}(A)=\text{span}\{(-2,1,0)^T\}$ , dimension 1.
Check rank–nullity: $2+1=3=n$ . ✔

Forecast-then-Verify

Flashcards

What is the column space of

A

The span of

A

's columns; equivalently all

b

for which

Ax=b

is solvable. Lives in

\mathbb{R}^m

What is the null space of

A

All

x

with

Ax=0

; the inputs mapped to zero. Lives in

\mathbb{R}^n

Define rank three equivalent ways.

(1)

\dim\text{Col}(A)

, (2) number of independent columns, (3) number of pivots (= number of independent rows).

State the rank–nullity theorem.

\text{rank}(A) + \dim\text{Null}(A) = n

(number of columns).

Why does rank–nullity hold?

Each column is either a pivot (→rank) or free (→one null-space basis vector); they partition all

n

columns.

To find a basis for Col(A), which columns do you take?

The pivot columns of the ORIGINAL

A

, not of the RREF.

Why doesn't Col(R) equal Col(A)?

Row operations change columns entrywise; they preserve dependence relations but not the column space itself.

A matrix is

m\times n

with

n>m

. What can you say about its null space?

rank

\le m < n

, so nullity

\ge n-m>0

: it always has a nonzero null space.

Do row operations change the null space?

No:

EAx=0 \iff Ax=0

for invertible

E

When is

Ax=b

solvable?

Exactly when

b\in\text{Col}(A)

When is a square

n\times n

matrix invertible in terms of rank/null space?

Full rank

n

and

\text{Null}(A)=\{0\}

ML: what does a nontrivial null space of the design matrix

X

imply?

Multicollinearity → non-unique least-squares weights (directions

w

with

Xw=0

Recall Feynman: explain to a 12-year-old

Imagine a photocopier that can only make copies using two ink colors mixed together. The column space is every color it can possibly print — its whole palette. The rank is how many truly different inks it has (if red and pink are basically the same, that's really one ink, not two). The null space is the secret recipe of ink amounts that prints a totally blank page — you mixed positive of one and negative of another so they cancel. If the machine has fewer real inks than knobs, there are always blank-page recipes: many different knob settings give the same picture.

Connections

Linear independence and span — rank is the size of a maximal independent set.
Solving linear systems (Ax=b) — solvability ⇔ $b\in\text{Col}(A)$ ; uniqueness ⇔ $\text{Null}(A)=\{0\}$ .
Gaussian elimination and RREF — the engine that reveals pivots.
Four fundamental subspaces — Col, Null, Row space, Left null space and their dimensions.
Least squares and normal equations — full column rank makes $X^TX$ invertible.
Invertible matrices and determinants — full rank ⇔ invertible ⇔ nonzero determinant.
SVD and low-rank approximation — rank counts nonzero singular values.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho ek matrix $A$ ek machine hai jo input vector $x$ ko $Ax$ me convert karti hai. Do sabse important sawaal: machine kya-kya output bana sakti hai (yeh hai column space — saare columns ka span), aur kaunse input ko zero bana deti hai (yeh hai null space). Rank batata hai ki machine ke paas asli me kitni alag-alag independent directions hain — agar do columns basically same hain (ek doosre ke multiple), to woh rank me count nahi hote.

Nikalna simple hai: matrix ko RREF tak row-reduce karo. Jitne pivots milenge, utna hi rank. Column space ke liye — pivot wale columns dekho, par original $A$ ke columns lena, RREF ke nahi (yeh sabse common galti hai). Null space ke liye — free variables ko parameter do aur back-substitute karke special solutions nikaalo.

Sabse pyaari cheez hai Rank–Nullity theorem: $\text{rank} + \text{nullity} = n$ (number of columns). Reason bilkul seedha — har column ya to pivot hai ya free; pivots rank dete hain, free columns null space ke basis vectors dete hain, aur inn dono ka total $n$ hi hoga.

ML me yeh kyun matter karta hai? Agar tumhare data matrix $X$ ka null space non-zero hai, matlab multicollinearity hai — kuch feature doosre features ka combination hain. Tab least-squares weights unique nahi rehte, kyunki $Xw=0$ wale directions prediction ko change hi nahi karte. Isliye rank samajhna model ke stability ke liye zaroori hai.

Test yourself — Linear Algebra Essentials

Connections