Fundamental Theorem of Linear Algebra

Recall some definitions:

• If A ∈ Mat_{k×n}, the column space of A is the span of the columns of A (in ℝ^{k}):

col(A) = Span{a_{1}, …, a_{n}} if A = [a_{1} ⋯ a_{n}] .

• The row space of A is the column space of A^{⊤}:

row(A) = col(A^{⊤}).

• The nullspace of A is the kernel of the map x ↦ Ax:

null(A) = {x ∈ ℝ^{n} | Ax = 0}.

• If V is a subspace of ℝ^{n}, then the orthogonal space or (orthogonal complement) of V is:

V^{⊥} = {x ∈ ℝ^{n} | v · x = 0 for all v ∈ V } = v_{1}^{⊥} ∩ ⋯ ∩ v_{ℓ}^{⊥} if {v_{i}} is a basis for V .

Fundamental Theorem of Linear Algebra. Let A be a k × n matrix. Then

null(A) = row(A)^{⊥} and null(A^{⊤}) = col(A)^{⊥}.

Moreover, if A has rank r (i.e., the echelon form of A has r pivotal 1s), then

dim(row(A)) = dim(col(A)) = r,
dim(null(A)) = n − r, and dim(null(A^{⊤})) = k − r.

Remark. The dimensions given in the statement above follow immediately from the dimension formula, covered in last week’s lecture. We’ll only prove the first part of the theorem.

Proof.Let b_{i}^{⊤}, 1 ≤ i ≤ k, be the rows of A, i.e.,

A = [b_{1}^{⊤} ; ⋮ ; b_{k}^{⊤}]

First, suppose x ∈ row(A)^{⊥}. Then v·x = 0 for every v ∈ row(A); in particular, b_{i} ·x = 0 for every i. By the definition of matrix multiplication, [Ax]_{i} = 0 for 1 ≤ i ≤ k. Therefore x ∈ null(A), which implies row(A)^{⊥} ⊂ null(A).

Now, suppose x ∈ null(A). Then, again by the definition of matrix multiplication, b_{i} · x = 0 for all i. If b ∈ row(A), then there exist scalars c_{1}, …, c_{k} such that b = c_{1}b_{1} + ⋯ + c_{k}b_{k}. Thus we compute:

b · x = (c_{1}b_{1} + ⋯ + c_{k}b_{k}) · x = c_{1}(b_{1} · x) + ⋯ + c_{k}(b_{k} · x) = 0 + ⋯ + 0 = 0.

Therefore x ∈ row(A)^{⊥}, which implies null(A) ⊂ row(A)^{⊥}.

We conclude null(A) = row(A)^{⊥}. The equality null(A^{⊤}) = col(A)^{⊥} follows immediately by applying the same argument to A^{⊤}, since by definition col(A) = row(A^{⊤}). □

Direct sums

The notion of a direct sum of subspaces is very important in linear algebra. First, let’s define the general sum: if V and W are subspaces of ℝ^{n}, then their sum is

V + W = {v + w | v ∈ V, w ∈ W }.

This definition says nothing about how V and W are related. One may be contained in the other, or they may have some large overlap. But if V ∩ W = {0}, then the sum has a special property, which you are to prove in the homework: every x in V + W has a unique expression as a vector in V plus a vector in W. To show this special relationship, we write V + W = V ⊕ W, and call V ⊕ W the direct sum of V and W.

Let’s see an important example: Example. If V is a subspace of ℝ^{n}, then ℝ^{n} = V ⊕ V^{⊥}.

Proof.Let v_{1}, …, v_{j} be a basis for V. Then V^{⊥} is the space of vectors x that solve the system

{v_{1} · x = 0 ; ⋮ ; v_{j} · x = 0 ,

by the Fundamental Theorem of Linear Algebra. By the rank-nullity theorem, the dimension of V^{⊥} is n − j. Every vector in V^{⊥} is linearly independent from V, so a basis for V^{⊥} together with a basis for V must span ℝ^{n}. But clearly V ∩ V^{⊥} = {0}, so ℝ^{n} = V ⊕ V^{⊥}. □

Remark. It now follows immediately from the Fundamental Theorem that, if A ∈ Mat_{k×n},

ℝ^{n} = null(A) ⊕ row(A),  and  ℝ^{k} = null(A^{⊤}) ⊕ col(A).

Graphing

We draw the graph of a function f : ℝ → ℝ in ℝ^{2}. But we’re using ℝ^{2} in a particular way: we definitely want to use the standard basis, and we want the x-direction to represent one copy of ℝ and the y-direction to represent another copy of ℝ. To make this distinction, we’ll write ℝ^{2} = ℝ ⊕ ℝ, meaning that ℝ^{2} is the direct sum of the x- and y-directions. The graph of f is the subset

G_{f} = \{(\begin{matrix}x \\ f(x) \end{matrix}) ∈ ℝ^{2} | x ∈ ℝ\} .

We thus generalize the notion of graph as follows: suppose f : ℝ^{n} → ℝ^{k}. Then we need n + k dimensions to draw the graph of f. Write ℝ^{n+k} = ℝ^{n} ⊕ ℝ^{k}, so that ℝ^{n} is identified with the first n variables in ℝ^{n+k}, and ℝ^{k} with the last k variables. Then the graph of f is

G_{f} = \{(\begin{matrix}x \\ f(x) \end{matrix}) ∈ ℝ^{n} ⊕ ℝ^{k} = ℝ^{n+k} | x ∈ ℝ^{n}\} .

Why is it so important to think about what we’re doing when graphing? Because we’re going to need to be able to switch perspectives. For example, any line through the origin in ℝ^{2} can be thought of as the graph of a linear function ℝ → ℝ. If it’s neither horizontal nor vertical, then we can think of the function as defining y in terms of x, or x in terms of y. If it is either horizontal or vertical, however, there’s only one option for the independent variable. With more variables, there are (sometimes) more choices. This is mostly a headsup; the real work of knowing how to change perspectives this way will come in a couple of weeks. The following theorem should begin to give you some insight.

Linear Implicit Function Theorem. Let T : ℝ^{n} → ℝ^{k} be a linear transformation, and assume T is onto. Set m = n − k. Then there is a linear function S : ℝ^{m} → ℝ^{k} defined implicitly by the kernel of T, i.e., ker(T) is the “graph” of S.

To get S, relabel the coordinates in ℝ^{n} (if necessary) so that the first k columns of [T] are pivotal. Then row reduce [T] to get 1s as coefficients for the first k variables in the corresponding system of equations. Write the equations, and transfer all non-pivotal variables to the other side of each equation.

There may be more than one choice for the pivotal variables. For example, in

[\begin{matrix}1 & 2 & −1 \\ 1 & 0 & 1 \end{matrix}]

any two of the columns are linearly independent, so any two can be made pivotal by relabeling. This is a 3 × 2 matrix, so there will be 2 pivotal variables and 1 non-pivotal variable; i.e., we’ll get a map ℝ → ℝ^{2}, whose graph is a line. Leaving them as they are, we get x_{1} and x_{2} in terms of x_{3}. The three possible functions ℝ → ℝ^{2} are:

\begin{cases}x_{1} = −x_{3} \\ x_{2} = x_{3} \end{cases} ,  \begin{cases}x_{1} = −x_{2} \\ x_{3} = x_{2} \end{cases} ,  and  \begin{cases}x_{2} = −x_{1} \\ x_{3} = −x_{1} \end{cases} .