Recent posts in Linear Algebra

🎯 What is Orthogonality?

Orthogonal is just a fancy word for perpendicular — a 90° angle.

This entire chapter is about:

• When are two vectors orthogonal?
• When are two subspaces orthogonal?
• When are bases orthogonal?

Example:

x = [1, 2, 3]
y = [1, -2, 1]

x·y = (1)(1) + (2)(-2) + (3)(1) = 1 - 4 + 3 = 0 ✅ ORTHOGONAL!

Check Pythagoras: x+y = [2, 0, 4]

||x+y||² = 4 + 0 + 16 = 20

||x||² + ||y||² = 14 + 6 = 20 ✅

Special note:

The zero vector is orthogonal to EVERY vector (0·y = 0 always)

2️⃣ Orthogonal Subspaces

Definition: Subspace S is orthogonal to subspace T means: $\boxed{\text{Every vector in S is perpendicular to every vector in T}}$ 

Common Mistake — Wall and Floor:

• The blackboard (a plane) and the floor (another plane) look perpendicular — but they are NOT orthogonal subspaces!
• Why? Because the line where they meet (the bottom of the board) is in BOTH subspaces.

A vector can't be perpendicular to itself (unless it's zero).

Key Rule: If two subspaces share any non-zero vector, they CANNOT be orthogonal

When ARE two subspaces orthogonal?

Two subspaces $S_1$ and $S_2$ are orthogonal if every vector $u \in S_1$ is orthogonal (perpendicular) to every vector $v \in S_2$. This means their dot product (or inner product) is zero, $u \cdot v = 0$ (or $u^T v = 0$) for all pairs of vectors. They share only the zero vector in common, i.e., $S_1 \cap S_2 = \{0\}$.

In 2D (the plane), possible subspaces are:

• The zero vector
• A line through origin
• The whole plane

Two lines through origin are orthogonal when they meet at exactly 90°. They only share the zero vector — that's what makes it work!

3️⃣ The Big Result: Row Space ⊥ Null Space

Statement: $\text{Row space of } A \perp \text{Null space of } A$

Proof (simple!): Take any vector x in the null space → Ax = 0

Write this out row by row:

[row 1 of A] · x = 0
[row 2 of A] · x = 0
      ⋮
[row m of A] · x = 0

• Each row is perpendicular to x!
• Now take any combination of rows: c₁(row 1) + c₂(row 2) + ... — that's any vector in the row space.

Is it perpendicular to x?

Now take any linear combination of rows:
\[
c_1(\text{row}_1 . x) + c_2(\text{row}_2 . x) + \ldots = c1​(0)+c2​(0)+…=0✓
\]

Therefore: Every vector in row space ⊥ every vector in null space ✅

Similarly (same proof for Aᵀ): $\boxed{\text{Column space of } A \perp \text{Left null space of } A}$

4️⃣ Orthogonal Complements

The null space doesn't just contain SOME vectors perpendicular to the row space — it contains ALL of them.

This is called being orthogonal complements:

Together they perfectly fill the entire space — no gaps, no overlaps (except at zero)

Visual:

        Rⁿ
   ┌─────────────────┐
   │   Row Space     │  dim = r
   │   (dim r)       │
   ├─────────────────┤  ← 90° between them
   │   Null Space    │  dim = n-r
   │   (dim n-r)     │
   └─────────────────┘
   r + (n-r) = n ✅

5️⃣ The Problem This Leads To

Real life gives us too many equations with noise:

Example — Satellite tracking:

• 1000 measurements (equations)
• Only 6 unknowns (position parameters)
• Each measurement has noise

So Ax = b has NO exact solution because b is contaminated with noise.

What do we do?

• Can't ignore equations (wasteful)
• Can't solve exactly (impossible)
• → Find the BEST POSSIBLE solution

The key equation that saves us: $\boxed{A^TA\hat{x} = A^Tb}$

Properties of AᵀA:

• Square: (n×m)(m×n) = n×n ✅
• Symmetric: (AᵀA)ᵀ = AᵀA ✅
• Invertible when: columns of A are independent ✅
• Rank of AᵀA = Rank of A (always!)

Some Important Points :

• AX=b → asks for exact solution
• $A^T A \hat{x} = A^T b$ → gives best possible approximation
• We use it when: 👉 AX=b has NO solution
• This happens when:b is not in the column space of A
• We find $\hat{x}$ such that: $A\hat{x} \approx b$ i.e., as close as possible
• This becomes a "best fit" problem
• We minimize error: $\|A\hat{x} - b\|^2$

This is called: 👉 Least Squares Problem

✅ That’s how the equation comes!

PROJECTIONS

        b
       /|
      / |  e = b - p
     /  |  (error, perpendicular to line)
    /   |
   /    ↓
  o-----p--------→ a
  
  p is on the line, e ⊥ a

$\boxed{x = \frac{a^T b}{a^T a}}$

The Projection Matrix:

     aa^T          ← (n×1)(1×n) = n×n MATRIX
P = ──────
     a^Ta          ← (1×n)(n×1) = scalar NUMBER

a₁ᵀ(b − Ax̂) = 0
a₂ᵀ(b − Ax̂) = 0
       ⋮
aₙᵀ(b − Ax̂) = 0

🔢 Two Extreme Cases

Case 1 — b is ALREADY in the column space: If b is in the column space → b = Ax for some x

$Pb = A(A^TA)^{-1}A^T \cdot Ax = A(A^TA)^{-1}(A^TA)x = Ax = b$

Result: Pb = b — projection leaves it unchanged ✅

Case 2 — b is PERPENDICULAR to the column space: If b ⊥ column space → b is in the null space of Aᵀ → Aᵀb = 0

$Pb = A(A^TA)^{-1}\underbrace{A^Tb}_{=0} = 0$

Result: Pb = 0 — projection kills it completely ✅

General Case (any b): Every vector b splits into two perpendicular parts: $\boxed{b = p + e}$

🔑 I − P is Also a Projection!

If P projects onto the column space, then (I − P) projects onto the perpendicular complement:

Algebra confirms what geometry already tells you!

LEAST SQUARES: FITTING A LINE

🎯 The Problem

Given 3 data points:

Find the best line: b = C + Dt

No line passes through all 3 points → find the best possible line.

🔢 Setting Up the Equations

For a perfect fit, we'd need:

C + D(1) = 1    →  C +  D = 1
C + D(2) = 2    →  C + 2D = 2
C + D(3) = 2    →  C + 3D = 2

Matrix form Ax = b:

$\underbrace{\begin{pmatrix}1 & 1 \\ 1 & 2 \\ 1 & 3\end{pmatrix}}_{A}
\underbrace{\begin{pmatrix}C \\ D\end{pmatrix}}_{x}
=
\underbrace{\begin{pmatrix}1 \\ 2 \\ 2\end{pmatrix}}_{b}$

3 equations, 2 unknowns → NO exact solution

🔢 What Does "Best" Mean?

Each equation gives an error:

e1 = (C + D)  − 1
e2 = (C + 2D) − 2
e3 = (C + 3D) − 2

Minimize the total squared error:

Minimize $ \|e\|^2 = e_1^2 + e_2^2 + e_3^2$. This is called Least Squares (also called Linear Regression in statistics)

⚠️ Note on outliers: Squaring amplifies large errors. One bad measurement (outlier) can distort the whole solution. Real statisticians handle this carefully!

🔢 Solving Using Normal Equations

The key equation: $A^T A \hat{x} = A^T b$

Step 1 — Compute $A^T A$: $A^T A =
\begin{pmatrix}
1 & 1 & 1 \\
1 & 2 & 3
\end{pmatrix}
\begin{pmatrix}
1 & 1 \\
1 & 2 \\
1 & 3
\end{pmatrix}
=
\begin{pmatrix}
3 & 6 \\
6 & 14
\end{pmatrix}$

Step 2 — Compute $A^T b$: $A^T b =
\begin{pmatrix}
1 & 1 & 1 \\
1 & 2 & 3
\end{pmatrix}
\begin{pmatrix}
1 \\
2 \\
2
\end{pmatrix}
=
\begin{pmatrix}
5 \\
11
\end{pmatrix}$

Step 3 — Solve the normal equations: $\begin{pmatrix}
3 & 6 \\
6 & 14
\end{pmatrix}
\begin{pmatrix}
C \\
D
\end{pmatrix}
=
\begin{pmatrix}
5 \\
11
\end{pmatrix}$

Using elimination:  $6C + 12D = 10$ , $6C + 14D = 11$

Subtracting: $2D = 1 \Rightarrow D = \frac{1}{2}$

Substitute back: $3C + 6\left(\frac{1}{2}\right) = 5 \Rightarrow 3C + 3 = 5 \Rightarrow C = \frac{2}{3}$

Best fit line: $b = \frac{2}{3} + \frac{1}{2} t$

🔢 Computing the Projection and Error

Values on the best line (projection p):

P1 = 2/3 + 1/2(1) = 7/6
P2 = 2/3 + 1/2(2) = 5/3
P3 = 2/3 + 1/2(3) = 13/6

$p = \begin{pmatrix}7/6\\5/3\\13/6\end{pmatrix}$ Error vector e = b − p: $e = \begin{pmatrix}1\\2\\2\end{pmatrix} - \begin{pmatrix}7/6\\5/3\\13/6\end{pmatrix} = \begin{pmatrix}-1/6\\2/6\\-1/6\end{pmatrix}$

✅ Verification — e ⊥ p: $p \cdot e = \frac{7}{6}\left(-\frac{1}{6}\right) + \frac{5}{3}\left(\frac{2}{6}\right) + \frac{13}{6}\left(-\frac{1}{6}\right)$

✅ Verification — e ⊥ entire column space: e must be perpendicular to every vector in the column space, not just p!

e · [1,1,1] = -1/6 + 2/6 - 1/6 = 0 ✅
e · [1,2,3] = -1/6 + 4/6 - 3/6 = 0 ✅

This confirms e is in the Left Null Space of A — perpendicular to the entire column space ✅

📐 Two Pictures of the Same Problem

Same math — two different ways to see it!

WHY AᵀA IS INVERTIBLE?

🎯 Key Theorem: $\boxed{A^T A \text{ is invertible} \iff \text{columns of } A \text{ are independent}}$

Goal: Show that if AᵀAx = 0, then x = 0

Step 1: Multiply both sides on left by xᵀ: $x^T A^T A x = 0$

Step 2: Rewrite using parentheses: $Ax)^T(Ax) = 0$

Step 3: This equals ‖Ax‖² = 0, so: Ax=0

Step 4: But columns of A are independent → null space of A = {0}: x=0✓

Therefore AᵀA has no non-zero null space → AᵀA is invertible ✅

ORTHONORMAL VECTORS & MATRICES

🎯 What Does Orthonormal Mean?

Vectors q₁, q₂, ..., qₙ are orthonormal when they are:

Combined into one neat condition: $ q_i^T q_j = \begin{cases} 1 & \text{if } i = j \\ 0 & \text{if } i \ne j \end{cases} $

Qᵀ has these vectors as ROWS
Q  has these vectors as COLUMNS

(QᵀQ)ᵢⱼ = (row i of Qᵀ) · (col j of Q)
         = qᵢᵀ · qⱼ
         = 0 (if i≠j) or 1 (if i=j)

🔑 Square vs Rectangular Q

By convention: only square Q with orthonormal columns is called an orthogonal matrix

📝 Examples of Orthogonal Matrices

Example 1 — Permutation matrix: $Q = \begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}$

Each column = a standard basis vector → unit vectors, perpendicular → orthogonal! ✅

Example 2 — Rotation matrix: $Q = \begin{pmatrix}\cos\theta & -\sin\theta \\ \sin\theta & \cos\theta\end{pmatrix}$

Both columns have length 1, dot product = 0 → orthogonal! ✅

WHY ORTHONORMAL COLUMNS MAKE LIFE EASY?

Verify the two projection properties:

• Symmetric? $(QQ^T)^T = (Q^T)^T Q^T = QQ^T \;\checkmark$
• P² = P? $(QQ^T)(QQ^T) = Q(\underbrace{Q^T Q}_{= I})Q^T = QQ^T \;\checkmark$

Special case — Q is square:

• Column space = all of Rⁿ → projection = identity
• $P = QQ^T = I \quad \text{(when $Q$ is square)}$

🎯 Normal Equations Simplify!

General normal equation: $A^T A \hat{x} = A^T b \quad \leftarrow \text{must solve a system}$

When A = Q: $Q^T Q \hat{x} = Q^T b \;\Rightarrow\; I\hat{x} = Q^T b \;\Rightarrow\; \boxed{\hat{x} = Q^T b}$

No matrix to invert — just compute dot products!

Each component of x̂: $\hat{x}_i = q_i^T b$

The i-th component = projection of b onto the i-th basis vector This is one of the most important formulas in mathematics!

GRAM-SCHMIDT PROCESS

b = (component along A) + (component ⊥ to A)
            ↓                      ↓
       (projection)            (what we want!)

Verify B ⊥ A: $$A^T B = A^T\!\left(b - \frac{A^T b}{A^T A}\,A\right)
= A^T b - \frac{A^T b}{A^T A}(A^T A)
= A^T b - A^T b
= 0 \;\checkmark$$

Step 3 — Normalize to get unit vectors: $\boxed{q_1 = \frac{A}{\|A\|}, \quad q_2 = \frac{B}{\|B\|}}$

⚠️ Square roots almost always appear here — unavoidable!

Three Vectors: Adding a Third

Given: A, B already orthogonal. Need C ⊥ A and C ⊥ B.

$\boxed{C = c - \frac{A^T c}{A^T A}\,A - \frac{B^T c}{B^T B}\,B}$

Logic: Start with c. Remove its A-component AND its B-component. What's left is perpendicular to both!

Then normalize:$\boxed{q_3 = \frac{C}{\|C\|}}$

📝 Numerical Example

Given:

a = [1, 1, 1]
b = [1, 0, 2]

Step 1 — A: $\begin{pmatrix}1 \\ 1 \\ 1\end{pmatrix}$

Step 2 — B: Compute:

• $A^T b = (1)(1) + (1)(0) + (1)(2) = 3$
• $A^T A = (1)(1) + (1)(1) + (1)(1) = 3$

\[
B = b - \frac{3}{3} A
= \begin{pmatrix}1 \\ 0 \\ 2\end{pmatrix}
- \begin{pmatrix}1 \\ 1 \\ 1\end{pmatrix}
= \begin{pmatrix}0 \\ -1 \\ 1\end{pmatrix}
\]

Check: \[
A^T B = (1)(0) + (1)(-1) + (1)(1) = 0 \;\checkmark
\]

Step 3 — Normalize:

\[
q_1 = \frac{A}{\|A\|} = \frac{1}{\sqrt{3}}
\begin{pmatrix}1 \\ 1 \\ 1\end{pmatrix},
\quad
q_2 = \frac{B}{\|B\|} = \frac{1}{\sqrt{2}}
\begin{pmatrix}0 \\ -1 \\ 1\end{pmatrix}
\]

Result: \[
Q =
\begin{pmatrix}
\frac{1}{\sqrt{3}} & 0 \\
\frac{1}{\sqrt{3}} & -\frac{1}{\sqrt{2}} \\
\frac{1}{\sqrt{3}} & \frac{1}{\sqrt{2}}
\end{pmatrix}
\]

Key observation:

• Column space of Q = same as column space of A
• Gram-Schmidt doesn't change the space — just rotates the basis to be orthonormal!

A = QR FACTORIZATION

Linear Algebra – Lecture 1

Topic: Solving Systems of Linear Equations

Example:

$$ A = \begin{bmatrix}
2 & 1 \\
5 & 3
\end{bmatrix} x = \begin{bmatrix}
1 \\
2
\end{bmatrix} $$
$$ \[
Ax =
\begin{bmatrix}
2 & 1 \\
5 & 3
\end{bmatrix}
\begin{bmatrix}
1 \\
2
\end{bmatrix}
=
\begin{bmatrix}
4 \\
11
\end{bmatrix}
\] $$

Way 1️⃣ — By COLUMNS ⭐ (Prof. Strang's Favourite)

Take 1 of column 1 + 2 of column 2

1 × [2]  +  2 × [5]  =  [2+10]  =  [12]
   [1]        [3]      [1+6]      [7]

Think of it as → linear combination of columns.

Way 2️⃣ — By ROWS (Dot Product)

Multiply each row with vector x separately

Row 1 → [2, 5] · [1, 2] = (2×1) + (5×2) = 2 + 10 = 12 

Row 2 → [1, 3] · [1, 2] = (1×1) + (3×2) = 1 + 6 = 7

Think of it as → dot product of each row with x

Linear Algebra – Lecture 2

Topic: Elimination, Back Substitution & Matrices

GOAL: Solve Ax = b using a method called Elimination → used by every software/computer

Step 1: Forward Elimination

Convert matrix A → U (Upper Triangular matrix)

When Does Elimination Fail?

• 0 in pivot position but non-zero below -> Row exchange → continue ✅
• 0 in pivot position AND zeros below -> Complete failure ❌ → matrix not invertible

 Step 2: Back Substitution

Solve the equations bottom to top (reverse order).

Augmented Matrix

Carry the right-hand side b along as an extra column during elimination.

[A | b]  →  [U | c]

• A becomes U
• b becomes c
• Then do back substitution on Ux = c

Elimination in Matrix Language

Each elimination step = multiplying by an Elementary Matrix E

Example — Subtract 3×(row1) from row2:

E₂₁ = | 1   0  0 |
       |-3   1  0 |
       | 0   0  1 |

• Identity rows for rows that don't change
• -3 in position (2,1) to do the subtraction

Permutation Matrix (P): Used to exchange rows when a 0 appears in the pivot position. Found by swapping rows of the Identity matrix.

Linear Algebra – Lecture 3

Topic: Matrix Multiplication & Inverses

Matrix Multiplication — 5 Ways

• All 5 ways give the same answer — just different perspectives!

C(3,4) = A(3,1)×B(1,4) + A(3,2)×B(2,4) + ...
Sum along the row of A and down the column of B

Way 2️⃣ — Column by Column ⭐

• Each column of C = A × (column of B)
• Columns of C are combinations of columns of A

 Way 3️⃣ — Row by Row

• Each row of C = (row of A) × B
• Rows of C are combinations of rows of B

Way 4️⃣ — Columns × Rows

A × B = (col1 of A × row1 of B) + (col2 of A × row2 of B) + ...

• Each piece gives a full-sized matrix
• Add them all up to get C

Way 5️⃣ — Block Multiplication

• Chop matrices into blocks
• Multiply blocks just like entries

C(block) = A1×B1 + A2×B3

Inverses

What is A⁻¹?

A⁻¹ is the matrix such that A⁻¹ × A = A × A⁻¹ = I

• Only square matrices can have inverses
• Left inverse = Right inverse (for square matrices)

When Does NO Inverse Exist? (Singular Matrix)

A matrix has no inverse if:

 💡Proof: If Ax = 0 for some x ≠ 0, then A⁻¹ cannot exist Because: A⁻¹(Ax) = x → but A⁻¹(0) = 0 → contradiction!

Gauss-Jordan Method to Find A⁻¹

Idea: Solve for all columns of A⁻¹ at the same time!

Steps:

1. Set up the augmented matrix → [ A | I ]

2. Do elimination on the left side until it becomes I

3. The right side automatically becomes A⁻¹

Start:   | 1  3 | 1  0 |
         | 2  7 | 0  1 |

Step 1 (subtract 2×row1 from row2):
         | 1  3 | 1   0 |
         | 0  1 |-2   1 |

Step 2 (subtract 3×row2 from row1):
         | 1  0 | 7  -3 |
         | 0  1 |-2   1 |

A⁻¹ =   | 7  -3 |
         |-2   1 |

Why Does Gauss-Jordan Work?

• All elimination steps together = one big matrix E => E × A = I → E must be A⁻¹

• So when E is applied to the right side (which started as I): E × I = A⁻¹ ✅

Linear Algebra – Lecture 4 & 5

2×2 Example:

A = |2  1|      L = |1  0|      U = |2  1|
    |8  7|          |4  1|          |0  3|

• L has 1s on diagonal
• L has the multipliers below diagonal (with + sign)
• U has the pivots on diagonal

Why Use LU Instead of Just Gaussian Elimination? -> 

• LU Decomposition : Compute L and U once → solve for any b cheaply ✅
• LU decomposition is independent of b (the right-hand side)!
• If matrix A can be reduced to row echelon form without swapping rows → LU exists

How to Solve Ax = b Using LU?

Step 1: Replace A with LU : 

LUx = b

Step 2: Let y = Ux → Solve Ly = b using forward substitution

L is lower triangular → solve top to bottom

Step 3: Solve Ux = y using back substitution 

U is upper triangular → solve bottom to top

Linear Algebra – Lecture 6

Subspaces

A subspace = a vector space living inside a larger vector space

Rules every subspace must follow:

1. Must contain the zero vector
2. Closed under addition
3. Closed under scalar multiplication

Examples in R³:

🔗 Union vs Intersection of Subspaces

Column Space C(A)

Column space = all linear combinations of the columns of A

• For an m × n matrix → column space is a subspace of Rᵐ
• It's the smallest subspace that contains all columns

Key Connection to Ax = b:

Ax=b has a solution⟺b is in the column space of A​

• If b = combination of columns → solution exists ✅
• If b is NOT in column space → no solution ❌

 Example (4×3 matrix):

• 3 columns in R⁴ → cannot fill all of R⁴
• Column 3 = Column 1 + Column 2 → dependent, adds nothing new
• Column space = 2D subspace of R⁴

Null Space N(A)

Null space = all vectors x that satisfy Ax = 0

• For an m × n matrix → null space is a subspace of Rⁿ
• Always contains the zero vector

Why is it a subspace? ✅

If Av = 0 and Aw = 0, then:

A(v + w) = Av + Aw = 0 + 0 = 0 ✅
A(12v) = 12(Av) = 12(0) = 0 ✅

A = |1  2  2  2|
    |2  4  6  8|
    |3  6  8  10|

U = |1  2  2  2|
    |0  0  2  4|
    |0  0  0  0|

x = [-2, 1, 0, 0]

x = [2, 0, -2, 1]

x = c₁[-2, 1, 0, 0] + c₂[2, 0, -2, 1]

R = |1  2  0  -2|
    |0  0  1   2|
    |0  0  0   0|

R = | I  F |
    | 0  0 |

Row 1 → x₁ = s + 4t
Row 2 → x₂ = -9t
Row 3 → x₄ = 2t

Linear Algebra – Lecture 10

Topic: The Four Fundamental Subspaces