Home / MLF / Week 3

Week 3 · Vectors, matrices and the best-fit line

Official syllabus line: Linear Algebra - Least Squares Regression

About 90 minQuiz 1 material (see exam radar)BSCS2004 · Harish Guruprasad Ramaswamy, Arun Rajkumar, Prashanth LA

Before you start: Week 1 (vectors, dot product, perpendicular). A little comfort solving two equations in two unknowns.

Watch first: the animated story of this weekAbout 1-2 minutes of real 3D animation with a friendly voice. Pause any time.

Read the words of the video

Imagine holding a pencil above a table, shining a flashlight straight down. The pencil's shadow on the table is its 'projection'. This shadow is the closest point on the table to your pencil's tip. The flashlight beam hits the table at a right angle, showing how we find the 'closest point equals perpendicular drop'. This is our main idea!
In machine learning, we often have data points that don't exactly sit on a straight line. We can't find a perfect solution. Instead, we find the line that is 'least wrong'. This 'least wrong' line is like the shadow of our data, found by dropping a perpendicular onto the set of things a line can produce. It's about finding the closest fit.
Let's try an example. Imagine a glowing point at (2,3) on a 2D graph and a glowing line passing through the origin at a 45-degree angle. We want to find the point's 'shadow' on this line. The shadow turns out to be at (2.5, 2.5). The difference between our original point and its shadow is exactly perpendicular to the line, just like our flashlight beam!
For exams, remember that projection matrices are symmetric and orthogonally diagonalisable, but they are not always orthogonal or rank one. Always think of projection as finding the 'closest point' or the 'shadow' of your data onto a line or surface. You've mastered finding the 'least wrong' answer! Great job!

The one-minute story

Think of it like this

You run a tiny shop and have recorded 3 days of sales: ads shown vs. items sold. The three dots almost sit on a line, but not quite. You want one straight line that is as close as possible to all three dots, so you can predict tomorrow.

No straight line passes through all three dots. So we cannot solve the problem exactly. What do we do? We find the line that is least wrong.

Here is the beautiful trick of this week: "least wrong" turns out to be the same thing as casting a shadow. The answer you want is the shadow of your real data on the set of things a line can produce. And shadows are found by dropping a perpendicular.

By the end of this week you can:

read a matrix as a machine that mixes vectors, and multiply matrices by vectors;
explain linear independence, span, basis, dimension and rank;
name the four fundamental subspaces and state their dimensions;
find the projection of a vector onto a line or a subspace;
fit a line (or any linear model) by least squares using the normal equations.

Words you need

Matrix - a rectangle of numbers. An $m\times n$ matrix has $m$ rows and $n$ columns.
Linear combination - "this much of vector A plus that much of vector B". Example: $2\mathbf a+3\mathbf b$ .
Span - everything you can build from some vectors using linear combinations.
Linearly independent - none of the vectors can be built from the others; each brings something new.
Basis - a smallest set of vectors that spans the space, i.e. independent and spanning.
Rank - how many independent columns a matrix has (the number of genuinely different directions it uses).
Projection - the shadow of a vector on a line or flat surface.
Residual - the leftover: the true value minus the fitted value.

Idea 1: A matrix mixes its columns

Think of it like this

Picture a juice bar with three juices: orange, apple, mango. A recipe says how many glasses of each go into a drink: $(2,1,0)$ means 2 orange, 1 apple, 0 mango. The matrix has one column per juice (what is in each juice: sugar, vitamin C, ...). Multiplying the matrix by a recipe vector gives the total nutrition: you mix the columns in the amounts the recipe says.

For $A=\begin{pmatrix}1&2\\3&4\end{pmatrix}$ and $\mathbf x=\begin{pmatrix}5\\6\end{pmatrix}$ :

A\mathbf x=5\begin{pmatrix}1\\3\end{pmatrix}+6\begin{pmatrix}2\\4\end{pmatrix}=\begin{pmatrix}17\\39\end{pmatrix}

Read $A\mathbf x$ as " $x_1$ times column 1, plus $x_2$ times column 2". Everything in this week follows from that single sentence.

The set of all possible $A\mathbf x$ (over all choices of $\mathbf x$ ) is called the column space of $A$ . It is exactly the span of the columns.

Two things to remember about shape: $A$ is $m\times n$ means it takes vectors with $n$ numbers and produces vectors with $m$ numbers. And $(AB)$ is allowed only when the inside sizes match: $(m\times n)(n\times p)=m\times p$ .

Idea 2: Independence, span, basis, dimension, rank

The idea

Vectors are linearly independent if the only way to mix them into the zero vector is to use zero of each. If one can be written from the others, they are dependent.
A basis of a space is a set of independent vectors that spans it. Every basis of the same space has the same number of vectors, called its dimension.
The rank of a matrix is the number of independent columns, which always equals the number of independent rows.

Example. $\begin{pmatrix}1\\2\end{pmatrix}$ and $\begin{pmatrix}2\\4\end{pmatrix}$ are dependent (the second is twice the first), so together they only span a line, not the whole plane. A $2\times2$ matrix with these as columns has rank 1.

The four fundamental subspaces

For an $m\times n$ matrix $A$ of rank $r$ :

Space	What it is	Lives in	Dimension
Column space	all $A\mathbf x$	$\mathbb R^m$	$r$
Row space	span of the rows	$\mathbb R^n$	$r$
Null space	all $\mathbf x$ with $A\mathbf x=\mathbf 0$	$\mathbb R^n$	$n-r$
Left null space	all $\mathbf y$ with $A^T\mathbf y=\mathbf 0$	$\mathbb R^m$	$m-r$

Two perpendicularity facts: row space $\perp$ null space, and column space $\perp$ left null space. Also rank + nullity = number of columns: $r+(n-r)=n$ .

Solved example: 1. Reading rank, nullity and dimensions

Question. $A$ is a $6\times4$ matrix with rank 4. Which statements are true? (a) the columns are independent; (b) the null space contains only $\mathbf 0$ ; (c) the row space is all of $\mathbb R^4$ ; (d) the left null space has dimension 2.

Solution. Rank 4 equals the number of columns, so all four columns are independent: (a) is true. Nullity $=n-r=4-4=0$ , so only the zero vector solves $A\mathbf x=\mathbf 0$ : (b) true. The row space has dimension 4 and lives in $\mathbb R^4$ , so it fills it: (c) true. Left null space has dimension $m-r=6-4=2$ : (d) true. All four are true.

The common slip is writing the left null space dimension as $n-r$ . It is $m-r$ (rows minus rank).

What a product does to row space and column space

Rows of $AB$ are mixtures of rows of $B$ ; columns of $AB$ are mixtures of columns of $A$ . So $\text{rowspace}(AB)\subseteq\text{rowspace}(B)$ and $\text{colspace}(AB)\subseteq\text{colspace}(A)$ , and $\text{rank}(AB)\le\min(\text{rank}A,\text{rank}B)$ . Papers love to swap $A$ and $B$ here.

Idea 3: Projection is a shadow

Think of it like this

Hold a pencil above a table and shine a torch straight down. The pencil's shadow on the table is its projection. The shadow is the point on the table closest to the pencil's tip, and the torch beam hits the table at a right angle. Closest point = perpendicular drop. Remember that sentence; it is the heart of the week.

Projection onto a line

Projecting $\mathbf x$ onto the line through the direction $\mathbf a$ :

\operatorname{proj}_{\mathbf a}(\mathbf x)=\frac{\mathbf a\cdot\mathbf x}{\mathbf a\cdot\mathbf a}\,\mathbf a,\qquad P=\frac{\mathbf a\mathbf a^T}{\mathbf a^T\mathbf a}

The matrix $P$ does the projecting for any $\mathbf x$ : $P\mathbf x=\operatorname{proj}_{\mathbf a}(\mathbf x)$ .

Why the formula looks like this: you want some multiple $c\,\mathbf a$ so that what is left over, $\mathbf x-c\mathbf a$ , is perpendicular to $\mathbf a$ . Perpendicular means dot product zero: $\mathbf a\cdot(\mathbf x-c\mathbf a)=0$ , so $c=\dfrac{\mathbf a\cdot\mathbf x}{\mathbf a\cdot\mathbf a}$ .

Solved example: 2. Projecting a point onto a line

Question. Project $\mathbf x=(2,3)$ onto the line through $\mathbf a=(1,1)$ . Then give the projection matrix onto the line $y=2x$ and its trace.

Solution.

$\mathbf a\cdot\mathbf x=5$ and $\mathbf a\cdot\mathbf a=2$ , so $c=\frac52$ and the shadow is $\frac52(1,1)=(2.5,\,2.5)$ .
The residual is $(2,3)-(2.5,2.5)=(-0.5,\,0.5)$ . Check perpendicular: $(1,1)\cdot(-0.5,0.5)=0$ .
The line $y=2x$ has direction $\mathbf a=(1,2)$ , so $P=\dfrac15\begin{pmatrix}1&2\\2&4\end{pmatrix}$ . Its trace is $\frac{1+4}{5}=\mathbf 1$ .

Notice $\text{trace}(P)=1$ : a projection onto a $k$ -dimensional subspace always has trace $k$ (its rank).

Four facts that every projection matrix obeys

$P^2=P$ (projecting twice changes nothing: the shadow of a shadow is itself);
$P^T=P$ (symmetric);
$P\mathbf v=\mathbf v$ for any $\mathbf v$ already on the line (it is its own shadow);
eigenvalues are only 0 and 1, and $\text{rank}(P)=\text{trace}(P)$ .

So a projection matrix is symmetric and orthogonally diagonalisable, but it is not an orthogonal matrix (it squashes things) and it is not always rank 1 (that depends on what you project onto). Those two sentences answer a real exam MSQ.

Projection onto a whole subspace

If the subspace is the column space of $A$ (columns independent), then

P=A(A^TA)^{-1}A^T

With one column $\mathbf a$ this collapses to $\mathbf a\mathbf a^T/(\mathbf a^T\mathbf a)$ , the line formula. Same idea; you just solve for several amounts at once.

Idea 4: Least squares, or "closest I can get"

You want $A\mathbf w=\mathbf y$ but $\mathbf y$ is not in the column space of $A$ (too many equations, too few unknowns, noisy data), so no exact solution exists. The best compromise is the point in the column space closest to $\mathbf y$ . That is the projection of $\mathbf y$ onto the column space.

The shadow $\hat{\mathbf y}=A\mathbf w$ is closest exactly when the leftover $\mathbf y-A\mathbf w$ is perpendicular to every column of $A$ :

A^T(\mathbf y-A\mathbf w)=\mathbf 0\;\;\Longrightarrow\;\;\boxed{A^TA\,\mathbf w=A^T\mathbf y}

These are the normal equations ("normal" meaning perpendicular). If the columns of $A$ are independent, $A^TA$ is invertible and

\mathbf w=(A^TA)^{-1}A^T\mathbf y,\qquad \hat{\mathbf y}=A(A^TA)^{-1}A^T\mathbf y=P\mathbf y.

Equivalently, $\mathbf w$ minimises the sum of squared errors $\|A\mathbf w-\mathbf y\|^2=\sum_i(\hat y_i-y_i)^2$ , the same squared loss you met in week 1. This is linear regression. For a line $y=c+dx$ we use a column of ones for the intercept $c$ and a column of $x$ -values for the slope $d$ .

Solved example: 3. Fitting a line to three points

Question. Fit $y=c+dx$ to the points $(0,1),\,(1,2),\,(2,2)$ .

Solution.

Build $A=\begin{pmatrix}1&0\\1&1\\1&2\end{pmatrix}$ (ones, then $x$ ) and $\mathbf y=\begin{pmatrix}1\\2\\2\end{pmatrix}$ .
$A^TA=\begin{pmatrix}3&3\\3&5\end{pmatrix}$ and $A^T\mathbf y=\begin{pmatrix}5\\6\end{pmatrix}$ .
Solve $\begin{pmatrix}3&3\\3&5\end{pmatrix}\begin{pmatrix}c\\d\end{pmatrix}=\begin{pmatrix}5\\6\end{pmatrix}$ . The determinant is $15-9=6$ , so $\begin{pmatrix}c\\d\end{pmatrix}=\frac16\begin{pmatrix}5&-3\\-3&3\end{pmatrix}\begin{pmatrix}5\\6\end{pmatrix}=\frac16\begin{pmatrix}7\\3\end{pmatrix}$ .
So $c=\frac76\approx1.17$ and $d=\frac12$ : the line is $\hat y=\frac76+\frac12x$ .
Fitted values: $1.17,\;1.67,\;2.17$ . Residuals: $-0.17,\;+0.33,\;-0.17$ .

Check: the residuals add to 0, and $A^T\mathbf r=\big(0,\;0\cdot(-\tfrac16)+1\cdot\tfrac13+2\cdot(-\tfrac16)\big)=(0,0)$ . The mistake vector is perpendicular to both columns, exactly as the theory says. The total squared error is $\frac1{36}+\frac19+\frac1{36}=\frac16$ .

Same problem, three languages

The idea

Geometry: $\hat{\mathbf y}$ is the projection of $\mathbf y$ onto the column space of $A$ .
Algebra: solve $A^TA\mathbf w=A^T\mathbf y$ .
Calculus: set the gradient of $\|A\mathbf w-\mathbf y\|^2$ to zero. You get the same equations. (We will use this in week 7.)

If $A$ has $m$ rows and $n$ independent columns with $m>n$ , then $A^TA$ is $n\times n$ and invertible. If the columns are dependent, $A^TA$ is not invertible and the best $\mathbf w$ is not unique. Later (MLT week 6) ridge regression fixes that.

Your turn

Your turn: 1. Dimensions of the four spaces

$A$ is a $5\times7$ matrix with rank 3. Give the dimension of each of the four fundamental subspaces.

Need a hint?

Use $r=3$ , $m=5$ , $n=7$ .

Show the full solution

Column space: $3$ . Row space: $3$ . Null space: $n-r=7-3=4$ . Left null space: $m-r=5-3=2$ .

Your turn: 2. Projection

Project $\mathbf x=(4,2)$ onto the direction $\mathbf a=(1,3)$ . Give the shadow and the length of the shadow.

Need a hint?

$c=\dfrac{\mathbf a\cdot\mathbf x}{\mathbf a\cdot\mathbf a}$ .

Show the full solution

$\mathbf a\cdot\mathbf x=4+6=10$ , $\mathbf a\cdot\mathbf a=10$ , so $c=1$ and the shadow is $(1,3)$ itself. Its length is $\sqrt{10}\approx3.16$ . Check the residual $(4,2)-(1,3)=(3,-1)$ is perpendicular to $(1,3)$ : $3-3=0$ .

Your turn: 3. Least squares by hand

Fit a line through the points $(1,2),\,(2,3),\,(3,5)$ .

Need a hint?

Set $A=\begin{pmatrix}1&1\\1&2\\1&3\end{pmatrix}$ , $\mathbf y=(2,3,5)^T$ and form $A^TA$ and $A^T\mathbf y$ .

Show the full solution

$A^TA=\begin{pmatrix}3&6\\6&14\end{pmatrix}$ , $A^T\mathbf y=\begin{pmatrix}10\\23\end{pmatrix}$ . The determinant is $42-36=6$ , so $\begin{pmatrix}c\\d\end{pmatrix}=\frac16\begin{pmatrix}14&-6\\-6&3\end{pmatrix}\begin{pmatrix}10\\23\end{pmatrix}=\frac16\begin{pmatrix}2\\9\end{pmatrix}$ . So $c=\frac13$ and $d=\frac32$ : $\hat y=\frac13+1.5x$ . Predictions at $x=1,2,3$ : $1.83,\;3.33,\;4.83$ .

Your turn: 4. Which statements about a projection matrix are true?

(a) symmetric (b) orthogonal (c) orthogonally diagonalisable (d) always rank 1

Need a hint?

Use the four facts listed in the lesson.

Show the full solution

(a) True, $P^T=P$ . (b) False: orthogonal matrices keep lengths, projections squash them. (c) True: symmetric matrices are orthogonally diagonalisable. (d) False: the rank equals the dimension of the subspace you project onto. Answer: (a) and (c).

Your turn: 5. Max dot product

$\|\mathbf a\|=3$ and $\|\mathbf b\|=5$ . What is the largest possible value of $|\mathbf a\cdot\mathbf b|$ ?

Need a hint?

Recall Cauchy-Schwarz from week 1.

Show the full solution

$|\mathbf a\cdot\mathbf b|\le\|\mathbf a\|\|\mathbf b\|=15$ , reached when they are parallel. Answer 15.

Exam radar

From the 53 MLF Quiz 1 papers: least squares method appears in 22, projection matrices in 13, row space in 11, basis in 11, rank in 9, matrix properties in 10, orthogonal matrix in 11.

Look for: rank/null-space MSQs (like Example 1), "find the projection matrix onto the line ...", "which statements about projection matrices are true", a small $X^TX$ calculation for least squares, and the house-price least-squares story in the newest papers.

Watch out - real exam trap

Left null space has dimension $m-r$ , not $n-r$ .
$\text{rowspace}(AB)\subseteq\text{rowspace}(B)$ but $\text{colspace}(AB)\subseteq\text{colspace}(A)$ . Do not swap.
Projection matrices are not orthogonal matrices.
In least squares, the residual is perpendicular to the columns of $A$ (the features), not to $\mathbf y$ .
$(A^TA)^{-1}$ exists only when the columns of $A$ are independent.

Quick quiz

A is 6 by 4 and has rank 4. What is the dimension of its left null space?

The left null space has dimension m - r = 6 - 4 = 2.

The projection matrix P onto the line through (1, 2) has trace...

P = (1/5)[[1,2],[2,4]], trace (1+4)/5 = 1. A projection onto a k-dimensional subspace always has trace k.

In least squares, the residual vector y - A w is...

parallel to y
equal to zero
perpendicular to every column of A
perpendicular to w

That is exactly the normal equation A^T (y - A w) = 0.

Select all TRUE statements about a projection matrix P. (select all that apply)

P squared equals P
P is symmetric
P is an orthogonal matrix
P always has rank 1

Projections are idempotent and symmetric. They are not orthogonal matrices, and the rank equals the dimension of the target subspace.

Recap

Remember this

$A\mathbf x$ = a mixture of the columns of $A$ . Rank = number of independent columns.
Four subspaces: column ( $r$ , in $\mathbb R^m$ ), row ( $r$ , in $\mathbb R^n$ ), null ( $n-r$ ), left null ( $m-r$ ). Row $\perp$ null; column $\perp$ left null.
Closest point = perpendicular drop. Projection onto a line: $\frac{\mathbf a\mathbf a^T}{\mathbf a^T\mathbf a}$ ; onto a column space: $A(A^TA)^{-1}A^T$ . Always $P^2=P=P^T$ .
Least squares: solve $A^TA\mathbf w=A^T\mathbf y$ . The fitted values are the projection of $\mathbf y$ ; the residual is perpendicular to the columns.

Formulas to keep

$A\mathbf x=x_1\,\text{col}_1+\dots+x_n\,\text{col}_n$
rank + nullity $=n$ ; left-null dimension $=m-r$
Projection onto line: $\frac{\mathbf a\cdot\mathbf x}{\mathbf a\cdot\mathbf a}\mathbf a$ ; matrix $\frac{\mathbf a\mathbf a^T}{\mathbf a^T\mathbf a}$
Projection onto $\text{col}(A)$ : $P=A(A^TA)^{-1}A^T$ ; $P^2=P=P^T$ ; $\text{rank}P=\text{trace}P$
Normal equations: $A^TA\mathbf w=A^T\mathbf y$ ; $\mathbf w=(A^TA)^{-1}A^T\mathbf y$
$\text{rank}(AB)\le\min(\text{rank}A,\text{rank}B)$

Connected weeks (learn them together)

MLT week 1 - PCA: finding the best view of your data: PCA's 'reconstruction' is a projection - exactly the shadow idea from MLF week 3.
MLT week 5 - Regression: least squares and its Bayesian view: Least-squares regression is the same problem as MLF week 3's best-fit line.
MLP week 3 - Linear regression and gradient descent in sklearn: The same least squares, now typed out in scikit-learn.

Practise with real exam questions

These come straight from past papers (with the real figures and the official answer key). Open 36 real questions on this week All Quiz 1 papers