Interactive guide · linear algebra

Systems and pseudoinverse

The system AX = b, the null space, the rank-nullity theorem and the right and left pseudoinverses. Every property has its step-by-step proof: click any card to see it.

Cumpără-mi o cafea

Deocamdată această secțiune este disponibilă doar în spaniolă și engleză.

Your system AX = b
A =
Rows Columns
b =
Examples
rank(A) = 2
2 equations and 3 unknowns.
dim Nul(A) = n − rank(A) = 3 − 2 = 1
Nul(A) is a line through the origin.
Which case you are in
  • Square with an inverse rank(A) = m = n
    Unique solution: X = A⁻¹b.
  • Right inverse rank(A) = m < n Your system
    Infinitely many solutions: X = Rb + Nul(A).
  • Left inverse rank(A) = n < m
    It can only be X = Lb, and it works if b is in Col(A).
  • Neither of them rank(A) < m and rank(A) < n
    There is no formula with pseudoinverses.
Inverse used

It exists because rank(A) = m: AR = I.

R = Aᵗ(AAᵗ)⁻¹
R =
2/3−1/31/31/3−1/32/3
Particular solution
Xp =
121

One specific solution of AX = b, the one you get by multiplying the inverse by b.

Basis of Nul(A)
v =
1−11

Every vector v satisfies Av = 0. Adding a multiple of it to a solution gives another solution.

Pick a solution

Move the sliders: X = Xp + Xh, with Xh in Nul(A).

Check
X =
121
AX =
33
b =
33

A·X equals b: it is a solution.

01 · The system AX = b

A system of equations as a matrix product

A system of linear equations can be written as a single equality between matrices. That way everything we know about matrices helps to solve it.

Coefficient matrix AIt has one row per equation and one column per unknown: its size is m × n (m equations, n unknowns).
Vector of unknowns XThe column (x1, …, xn) with what we are looking for.
Constant terms bThe column of numbers to the right of the equals sign, of size m × 1.
SolutionA vector X with AX = b. There may be none, one or infinitely many.
Homogeneous systemThe one with b = 0, that is, AX = 0. It always has the solution X = 0.
  1. 1Worked example (the one in the notes). Two equations and three unknowns:{x1+x2=3x2+x3=3\begin{cases} x_1 + x_2 = 3 \\ x_2 + x_3 = 3 \end{cases}
  2. 2Each row of A holds the coefficients of one equation. Multiplying row by column reproduces the left side:(110011)(x1x2x3)=(x1+x2x2+x3)\begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} x_1 + x_2 \\ x_2 + x_3 \end{pmatrix}
  3. 3Setting it equal to the right side gives the system in matrix form, AX = b:(110011)(x1x2x3)=(33)\begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 3 \\ 3 \end{pmatrix}
  4. 4We check with X = (1, 2, 1): 1 + 2 = 3 and 2 + 1 = 3. It is a solution, but we will see that it is not the only one.(110011)(121)=(33)\begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}\begin{pmatrix} 1 \\ 2 \\ 1 \end{pmatrix} = \begin{pmatrix} 3 \\ 3 \end{pmatrix}

What it is for. Writing AX = b lets us talk about all systems at once and use rank, inverses and pseudoinverses to decide how many solutions they have and to compute them.

02 · Null space

The null space Nul(A)

It is the set of all vectors that A turns into the zero vector. It is also called the kernel.

Nul(A)Nul(A) = {X : AX = 0}: all the solutions of the homogeneous system.See proof
  1. 1Example from the notes. AX = 0 is two equations in three unknowns:{x1+x2=0x2+x3=0\begin{cases} x_1 + x_2 = 0 \\ x_2 + x_3 = 0 \end{cases}
  2. 2One unknown is left free: x₂ = t. We solve x₁ = −t and x₃ = −t.x2=t,x1=−t,x3=−tx_2 = t, \quad x_1 = -t, \quad x_3 = -t
  3. 3We take t out as a common factor:Nul⁡(A)=t (−1, 1, −1)\operatorname{Nul}(A) = t\,(-1,\ 1,\ -1)
  4. 4We check: A·(−1, 1, −1) = (0, 0).(110011)(−11−1)=(00)\begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}\begin{pmatrix} -1 \\ 1 \\ -1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}

It is a line through the origin. The vector (1, −1, 1) used by the tool above describes the same line: just take t = −1.

What it is for. The null space collects «what is left over» in a system: the vectors that can be added to a solution without changing it. That is why it explains why there are infinitely many solutions.

The null space Nul(A): an example

A=(110011):Nul⁡(A)={ t (−1, 1, −1):t∈R }A = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}:\quad \operatorname{Nul}(A) = \{\, t\,(-1,\ 1,\ -1) : t \in \mathbb{R} \,\}

All the X with AX = 0. For A = (1 1 0; 0 1 1) they are the multiples of (−1, 1, −1).

See proof
03 · Dimension

Dimension and the rank-nullity theorem

The dimension measures the «size» of a set of vectors: in how many directions you can move inside it.

DimensionNumber of free letters (t, s, …) needed to write all the vectors of the set.
A pointDimension 0: no letters, you cannot move.
A lineDimension 1: one letter, X = t·v.
A planeDimension 2: two letters, X = s·v + t·w.
Rank-nullity theoremdim Nul(A) = n − rank(A): the unknowns left free are the unknowns minus the useful equations.See why
  1. 1Example with the A of the notes: n = 3 unknowns and rank 2 (the two rows are independent).n=3,r=2n = 3,\quad r = 2
  2. 2By the theorem, one unknown is left free.dim⁡Nul⁡(A)=n−r=3−2=1\dim\operatorname{Nul}(A) = n - r = 3 - 2 = 1
  3. 3It matches what we saw: Nul(A) = t(−1, 1, −1), a line, dimension 1.Nul⁡(A)=t (−1, 1, −1)\operatorname{Nul}(A) = t\,(-1,\ 1,\ -1)

If the rank equals the number of rows (m) and there are more columns than rows, then dim Nul(A) = n − m > 0: there are spare unknowns, the null space has free letters and the system has infinitely many solutions. What it is for. It tells you beforehand how many free directions the set of solutions has, without solving anything.

Dimension: how many free letters you need

dim⁡{0}=0,dim⁡{ tv }=1,dim⁡{ sv+tw }=2\dim\{0\} = 0,\qquad \dim\{\,tv\,\} = 1,\qquad \dim\{\,sv + tw\,\} = 2

A point has dimension 0, a line 1 and a plane 2: they are the free letters (t, s, …) of their vectors.

See proof

Rank-nullity theorem: dim Nul(A) = n − r

dim⁡Nul⁡(A)=n−r\dim\operatorname{Nul}(A) = n - r

The free unknowns are the unknowns minus the useful equations (the rank). Here r = rank(A).

See proof
04 · Right pseudoinverse

More unknowns than equations: R

A pseudoinverse is a matrix that acts as an inverse on one side only, useful when A is not square and has no true inverse. For an m × n matrix A with real entries:

On the rightAR = Im. It exists only if the rank is full by rows: rank(A) = m.
FormulaR = Aᵗ(AAᵗ)⁻¹. Its size is n × m.See where it comes from
Particular solution XpXp = Rb: one concrete solution of AX = b.See why
Homogeneous solution XhAny vector of the null space: A·Xh = 0. It is what is «left over» from a solution: Xh = X − Rb.See why
All the solutionsX = Xp + Xh = Rb + Nul(A).See why
  1. 1Worked example with the A of the notes and b = (3, 3). First AAᵗ, which is 2×2 and invertible because the rank is 2:AAt=(2112),(AAt)−1=13(2−1−12)AA^t = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix},\quad (AA^t)^{-1} = \dfrac{1}{3}\begin{pmatrix} 2 & -1 \\ -1 & 2 \end{pmatrix}
  2. 2The right pseudoinverse:R=At(AAt)−1=13(2−111−12)R = A^t(AA^t)^{-1} = \dfrac{1}{3}\begin{pmatrix} 2 & -1 \\ 1 & 1 \\ -1 & 2 \end{pmatrix}
  3. 3We check AR = I:AR=13(3003)=(1001)AR = \dfrac{1}{3}\begin{pmatrix} 3 & 0 \\ 0 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}
  4. 4Particular solution: Xp = Rb (sizes 3×2 times 2×1 = 3×1).Xp=Rb=13(2−111−12)(33)=(121)X_p = Rb = \dfrac{1}{3}\begin{pmatrix} 2 & -1 \\ 1 & 1 \\ -1 & 2 \end{pmatrix}\begin{pmatrix} 3 \\ 3 \end{pmatrix} = \begin{pmatrix} 1 \\ 2 \\ 1 \end{pmatrix}
  5. 5Any other solution, for example X = (0, 3, 0) (check that AX = (3, 3)). What is left over compared to Xp lies in the null space:Xh=X−Rb=(0,3,0)−(1,2,1)=(−1,1,−1)∈Nul⁡(A)X_h = X - Rb = (0, 3, 0) - (1, 2, 1) = (-1, 1, -1) \in \operatorname{Nul}(A)
  6. 6All the solutions: the line through Xp in the direction of the null space. With t = 0, 1, 2 we get (1, 2, 1), (0, 3, 0) and (−1, 4, −1).X=(1,2,1)+t (−1,1,−1)X = (1, 2, 1) + t\,(-1, 1, -1)

What it is for. It solves systems with more unknowns than equations and full rank, which always have a solution, and describes all of them with a single formula. It can also be proved that Rb is the shortest of all the solutions.

When AAᵗ and AᵗA have an inverse

r=m  ⇒  ∃ (AAt)−1r = m \;\Rightarrow\; \exists\,(AA^t)^{-1}

If the rank is m, AAᵗ (m×m) has an inverse; if it is n, AᵗA (n×n) has one. Here r = rank(A).

See proof

Right pseudoinverse: R = Aᵗ(AAᵗ)⁻¹

AR=Im  ⇒  R=At(AAt)−1AR = I_m \;\Rightarrow\; R = A^t(AA^t)^{-1}

If the rank is m, there is an R with AR = Im, computed as Aᵗ(AAᵗ)⁻¹. Here r = rank(A).

See proof

Particular solution: Xp = Rb

Xp=Rb  ⇒  AXp=bX_p = Rb \;\Rightarrow\; AX_p = b

If AR = I, the vector Rb always solves AX = b.

See proof

Homogeneous solution: Xh = X − Rb is in the null space

AX=b  ⇒  Xh=X−Rb∈Nul⁡(A)AX = b \;\Rightarrow\; X_h = X - Rb \in \operatorname{Nul}(A)

The difference between any solution and Rb satisfies A·Xh = 0.

See proof

All the solutions: X = Rb + Nul(A)

AX=b  ⟺  X=Rb+Xh,Xh∈Nul⁡(A)AX = b \iff X = Rb + X_h,\quad X_h \in \operatorname{Nul}(A)

The solutions of AX = b are a particular solution plus any vector of the null space.

See proof
05 · Left pseudoinverse

More equations than unknowns: L

Now the full rank is by columns: the n columns of A are independent. It is the opposite case to the previous one.

On the leftLA = In. It exists only if rank(A) = n. We say that A is injective (one to one): two different vectors never give the same result.
FormulaL = (AᵗA)⁻¹Aᵗ. Its size is n × m.See where it comes from
Solution X = LbIf the system has a solution, it is unique and equals Lb: the null space is Nul(A) = {0}.See why
Col(A)The column space (or image): all the vectors that can be formed by combining the columns of A.
When is Lb valid?Only if b ∈ Col(A). Otherwise Lb solves nothing and the system has no solution.See why
  1. 1Worked example: A is 3×2 with independent columns (rank 2 = n).A=(100111),AtA=(2112),(AtA)−1=13(2−1−12)A = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{pmatrix},\quad A^tA = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix},\quad (A^tA)^{-1} = \dfrac{1}{3}\begin{pmatrix} 2 & -1 \\ -1 & 2 \end{pmatrix}
  2. 2The left pseudoinverse (size 2×3):L=(AtA)−1At=13(2−11−121)L = (A^tA)^{-1}A^t = \dfrac{1}{3}\begin{pmatrix} 2 & -1 & 1 \\ -1 & 2 & 1 \end{pmatrix}
  3. 3We check LA = I:LA=13(3003)=(1001)LA = \dfrac{1}{3}\begin{pmatrix} 3 & 0 \\ 0 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}
  4. 4With b = (1, 2, 3), which is in Col(A) (3 = 1 + 2), we get the unique solution:X=Lb=13(2−11−121)(123)=(12)X = Lb = \dfrac{1}{3}\begin{pmatrix} 2 & -1 & 1 \\ -1 & 2 & 1 \end{pmatrix}\begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix} = \begin{pmatrix} 1 \\ 2 \end{pmatrix}
  5. 5With b′ = (1, 2, 0), which is NOT in Col(A), Lb′ = (0, 1) is not a solution: A(Lb′) = (0, 1, 1) ≠ b′.A(Lb′)=(011)≠(120)=b′A(Lb') = \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix} \neq \begin{pmatrix} 1 \\ 2 \\ 0 \end{pmatrix} = b'

What it is for. With more equations than unknowns (for example, many measurements for few parameters), L finds the only candidate solution, and the check A(Lb) = b tells whether it really is one. When it is not, the next step is least squares.

Left pseudoinverse: L = (AᵗA)⁻¹Aᵗ

LA=In  ⇒  L=(AtA)−1AtLA = I_n \;\Rightarrow\; L = (A^tA)^{-1}A^t

If the rank is n, there is an L with LA = In, computed as (AᵗA)⁻¹Aᵗ. Here r = rank(A).

See proof

With L the solution is unique: X = Lb

LA=I  ⇒  (AX=b⇒X=Lb)LA = I \;\Rightarrow\; (AX = b \Rightarrow X = Lb)

If LA = I and the system has a solution, it can only be Lb: the null space is {0}. Here r = rank(A).

See proof

Lb is a solution if and only if b is in Col(A)

A(Lb)=b  ⟺  b∈Col⁡(A)A(Lb) = b \iff b \in \operatorname{Col}(A)

Col(A) is the set of combinations of the columns of A. If b is not there, the system has no solution.

See proof
06 · Summary

The four cases

Depending on the rank of A, the system AX = b falls into one of these cases. Click the ones with a proof.

Left · LA = Irank(A) = n (full columns, A injective). Solution X = Lb, unique, and only if b is in Col(A): at most one solution.See why
Right · AR = Irank(A) = m (full rows, A surjective). Solution X = Rb + Nul(A): there is always at least one, and infinitely many if there are more columns than rows.See why
Both · L = R = A⁻¹A square and regular (rank(A) = m = n). Solution X = A⁻¹b, unique and always exists.See why
Neither · A⁺The rank is below both m and n. We look for the solution that minimises the error ‖AX − b‖ (least squares, with the Moore-Penrose pseudoinverse A⁺). It is outside these notes.

If A is square and regular, R = L = A⁻¹

r=m=n  ⇒  R=L=A−1r = m = n \;\Rightarrow\; R = L = A^{-1}

When m = n = r, both pseudoinverses coincide with the usual inverse. Here r = rank(A).

See proof

What it is for. It is the map so you do not get lost: compute the rank of A, check whether it equals m, n or both, and that tells you which formula to use and how many solutions to expect.

07 · Applications

What is the pseudoinverse for?

Fitting dataMany measurements and few parameters: more equations than unknowns. It is the case of L, and the step before least squares.
RoboticsAn arm with more joints than coordinates to reach has infinitely many solutions; Rb picks one (the one with the least movement).
Networks and flowsDistributing a flow among many paths: there is a particular solution plus a family of adjustments that do not change the total (the null space).
Compression and signalsReconstructing a signal with fewer data than values: there are infinitely many possibilities and one is chosen with the pseudoinverse.
Knowing whether a system is consistentChecking whether b is in Col(A) answers the question «does it have a solution?» without solving the whole system.
Proof

The null space Nul(A): an example

A=(110011):Nul⁡(A)={ t (−1, 1, −1):t∈R }A = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}:\quad \operatorname{Nul}(A) = \{\, t\,(-1,\ 1,\ -1) : t \in \mathbb{R} \,\}
  1. AX=0  ⟺  {x1+x2=0x2+x3=0AX = 0 \;\Longleftrightarrow\; \begin{cases} x_1 + x_2 = 0 \\ x_2 + x_3 = 0 \end{cases}

    The null space Nul(A) is the set of all X with AX = 0. For A = (1 1 0; 0 1 1) and X = (x₁, x₂, x₃), AX = 0 is two equations: x₁ + x₂ = 0 and x₂ + x₃ = 0.

  2. x2=tx_2 = \hl{t}

    There are 3 unknowns and only 2 equations, so one is left free. We choose x₂ = t, where t is any real number.

  3. x1=−t,x3=−tx_1 = -t,\qquad x_3 = -t

    We solve for the other two: x₁ = −x₂ = −t and x₃ = −x₂ = −t.

  4. X=(−t, t, −t)=t (−1, 1, −1)X = (-t,\ t,\ -t) = t\,(-1,\ 1,\ -1)

    We take t out as a common factor: every vector of the null space is a multiple of (−1, 1, −1). That is, Nul(A) = t(−1, 1, −1). (If you prefer the vector (1, −1, 1), it describes the same line: just take t = −1.)

  5. A(−11−1)=(−1+1+00+1−1)=(00)A\begin{pmatrix} -1 \\ 1 \\ -1 \end{pmatrix} = \begin{pmatrix} -1 + 1 + 0 \\ 0 + 1 - 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}

    We check with the vector (−1, 1, −1): A·(−1, 1, −1) = (−1 + 1 + 0, 0 + 1 − 1) = (0, 0).

  6. A(tv)=t (Av)=t⋅0=0,A(u+v)=Au+Av=0A(tv) = t\,(Av) = t \cdot 0 = 0,\qquad A(u + v) = Au + Av = 0

    Why it is a “space”: if Av = 0, then A(tv) = t·Av = 0 for any t; and if u and v satisfy Au = Av = 0, then A(u + v) = 0 too. Here it is a line through the origin.

What it's for

The null space collects “what is left over”: the vectors that A turns into 0. Adding them to a solution does not change the result, which is why they explain how a system can have infinitely many solutions.

Proof

Dimension: how many free letters you need

dim⁡{0}=0,dim⁡{ tv }=1,dim⁡{ sv+tw }=2\dim\{0\} = 0,\qquad \dim\{\,tv\,\} = 1,\qquad \dim\{\,sv + tw\,\} = 2
  1. X=0X = 0

    The dimension is the number of free letters (t, s, …) you need to write all the vectors of a set; that is, in how many directions you can move. A point, the vector 0: no letters, dimension 0. You cannot move.

  2. X=t vX = t\,v

    A line through the origin: X = t·v. One letter, dimension 1: you can only go forwards or backwards in one direction.

  3. X=s v+t w,v∦wX = s\,v + t\,w,\qquad v \nparallel w

    A plane through the origin: X = s·v + t·w with v and w not parallel (if they were, there would be only one direction). Two letters, dimension 2.

  4. Nul⁡(A)={ t (−1, 1, −1) }  ⇒  dim⁡=1\operatorname{Nul}(A) = \{\, t\,(-1,\ 1,\ -1) \,\} \;\Rightarrow\; \dim = 1

    The Nul(A) of the previous demonstration is t(−1, 1, −1): one letter, dimension 1. It is a line.

  5. x1+x2+x3=0:x2=s, x3=t, x1=−s−tx_1 + x_2 + x_3 = 0:\quad x_2 = s,\ x_3 = t,\ x_1 = -s - t

    Another example: x₁ + x₂ + x₃ = 0 (a single equation and 3 unknowns). We leave x₂ = s and x₃ = t free; then x₁ = −s − t.

  6. X=s (−1, 1, 0)+t (−1, 0, 1)  ⇒  dim⁡=2X = s\,(-1,\ 1,\ 0) + t\,(-1,\ 0,\ 1) \;\Rightarrow\; \dim = 2

    X = s(−1, 1, 0) + t(−1, 0, 1): two letters, dimension 2, a plane. Check: (−1, 1, 0) and (−1, 0, 1) add up to −1 + 1 + 0 = 0 and −1 + 0 + 1 = 0.

What it's for

It measures the “size” of a set of solutions: dimension 0 is a single solution, 1 a line of solutions, 2 a plane of solutions.

Proof

Rank-nullity theorem: dim Nul(A) = n − r

dim⁡Nul⁡(A)=n−r\dim\operatorname{Nul}(A) = n - r
  1. A=(120100111212)∼(120100110000)A = \begin{pmatrix} 1 & 2 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 2 & 1 & 2 \end{pmatrix} \sim \begin{pmatrix} 1 & 2 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}

    We take a 3×4 matrix A (3 equations and 4 unknowns) and reduce it: R₃ ← R₃ − R₁ and then R₃ ← R₃ − R₂ make the third row vanish.

  2. r=2r = 2

    2 non-zero rows are left: the rank is r = 2. The pivots are in columns 1 and 3.

  3. n−r=4−2=2  ⇒  x2=s, x4=tn - r = 4 - 2 = 2 \;\Rightarrow\; x_2 = \hl{s},\ x_4 = \hl{t}

    The unknowns without a pivot (x₂ and x₄) stay free: n − r = 4 − 2 = 2. We call them s and t.

  4. x1+2x2+x4=0,x3+x4=0  ⇒  x1=−2s−t, x3=−tx_1 + 2x_2 + x_4 = 0,\quad x_3 + x_4 = 0 \;\Rightarrow\; x_1 = -2s - t,\ x_3 = -t

    The remaining equations are x₁ + 2x₂ + x₄ = 0 and x₃ + x₄ = 0. Solving for the unknowns with a pivot: x₁ = −2s − t and x₃ = −t.

  5. X=s (−2, 1, 0, 0)+t (−1, 0, −1, 1)  ⇒  dim⁡Nul⁡(A)=2X = s\,(-2,\ 1,\ 0,\ 0) + t\,(-1,\ 0,\ -1,\ 1) \;\Rightarrow\; \dim\operatorname{Nul}(A) = 2

    X = s(−2, 1, 0, 0) + t(−1, 0, −1, 1): two free letters, so dim Nul(A) = 2. Check: A·(−2, 1, 0, 0) = (−2 + 2, 0, −2 + 2) = (0, 0, 0).

  6. dim⁡Nul⁡(A)=n−r\dim\operatorname{Nul}(A) = n - r

    In general, dim Nul(A) = n − r: unknowns minus useful equations. The rank counts the equations that are not redundant.

What it's for

It tells you, before solving anything, how many free directions the set of solutions has. If r = m and there are more columns than rows, n − m > 0 and the system has infinitely many solutions.

Proof

When AAᵗ and AᵗA have an inverse

r=m  ⇒  ∃ (AAt)−1r = m \;\Rightarrow\; \exists\,(AA^t)^{-1}
  1. A⏟m×n At⏟n×m=AAt⏟m×m\underbrace{A}_{m \times n}\ \underbrace{A^t}_{n \times m} = \underbrace{AA^t}_{m \times m}

    If A is m×n, Aᵗ is n×m, so AAᵗ is square of size m×m. Being square is necessary to have an inverse; we still have to see when it has one.

  2. AAtx=0  ⇒  xtAAtx=0AA^t x = 0 \;\Rightarrow\; x^tAA^tx = 0

    Suppose (AAᵗ)x = 0 and we want to show that x = 0. We multiply by xᵗ on the left.

  3. xtAAtx=(Atx)t(Atx)=∥Atx∥2=0x^tAA^tx = (A^tx)^t(A^tx) = \|A^tx\|^2 = 0

    Since (Aᵗx)ᵗ = xᵗA, we get xᵗAAᵗx = (Aᵗx)ᵗ(Aᵗx) = ‖Aᵗx‖², the sum of the squares of the entries of the vector Aᵗx.

  4. ∥Atx∥2=0  ⇒  Atx=0\|A^tx\|^2 = 0 \;\Rightarrow\; A^tx = 0

    A sum of squares of real numbers is 0 only if every term is 0 (this uses that A is real): Aᵗx = 0.

  5. rAt=r=m  ⇒  dim⁡Nul⁡(At)=m−m=0  ⇒  x=0r_{A^t} = r = m \;\Rightarrow\; \dim\operatorname{Nul}(A^t) = m - m = 0 \;\Rightarrow\; x = 0

    Aᵗ is n×m and its rank is r = m (rank(A) = rank(Aᵗ)). By the rank-nullity theorem, dim Nul(Aᵗ) = m − m = 0: Aᵗx = 0 only happens for x = 0.

  6. Nul⁡(AAt)={0}  ⇒  rAAt=m  ⇒  ∃ (AAt)−1\operatorname{Nul}(AA^t) = \{0\} \;\Rightarrow\; r_{AA^t} = m \;\Rightarrow\; \exists\,(AA^t)^{-1}

    We have seen that AAᵗx = 0 forces x = 0, that is, Nul(AAᵗ) = {0}. By rank-nullity, its rank rank(AAᵗ) is m and, being square, it has an inverse. (If r < m it does not: the rank of a product does not exceed that of its factors.)

  7. r=n  ⇒  ∃ (AtA)−1r = n \;\Rightarrow\; \exists\,(A^tA)^{-1}

    The same goes for AᵗA, of size n×n, when r = n: just apply the above to Aᵗ instead of A.

What it's for

It is the reason why the pseudoinverse formulas work: without full rank neither AAᵗ nor AᵗA can be inverted. All of this is for matrices of real numbers.

Proof

Right pseudoinverse: R = Aᵗ(AAᵗ)⁻¹

AR=Im  ⇒  R=At(AAt)−1AR = I_m \;\Rightarrow\; R = A^t(AA^t)^{-1}
  1. R=At Cm×mR = A^t\,C_{m \times m}

    We look for R (of size n×m) with AR = Im. Idea: build R from Aᵗ, because then a square product appears that we do know how to invert. We write R = AᵗC, with C an m×m matrix to be determined.

  2. AR=(AAt) C=IAR = (AA^t)\,C = I

    We substitute: AR = A·AᵗC = (AAᵗ)C, and we want it to equal I.

  3. C=(AAt)−1(r=m)C = (AA^t)^{-1} \qquad (r = m)

    AAᵗ is m×m and, since the rank of A is m, it has an inverse (previous demonstration). Multiplying by it: C = (AAᵗ)⁻¹.

  4. R=AtC=At(AAt)−1R = A^tC = A^t(AA^t)^{-1}

    Back to R = AᵗC, substituting C: R = Aᵗ(AAᵗ)⁻¹.

  5. AR=AAt(AAt)−1=IAR = AA^t(AA^t)^{-1} = I

    Check: AR = AAᵗ(AAᵗ)⁻¹ = I.

  6. AAt=(2112),(AAt)−1=13(2−1−12)AA^t = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix},\quad (AA^t)^{-1} = \dfrac{1}{3}\begin{pmatrix} 2 & -1 \\ -1 & 2 \end{pmatrix}

    Example with A = (1 1 0; 0 1 1): AAᵗ = (2 1; 1 2), with det = 3, and its inverse is (1/3)(2 −1; −1 2).

  7. R=At(AAt)−1=13(2−111−12)R = A^t(AA^t)^{-1} = \dfrac{1}{3}\begin{pmatrix} 2 & -1 \\ 1 & 1 \\ -1 & 2 \end{pmatrix}

    R = Aᵗ(AAᵗ)⁻¹ = (1/3)(2 −1; 1 1; −1 2). It is a 3×2 matrix: n×m.

  8. AR=13(110011)(2−111−12)=13(3003)=I2AR = \dfrac{1}{3}\begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}\begin{pmatrix} 2 & -1 \\ 1 & 1 \\ -1 & 2 \end{pmatrix} = \dfrac{1}{3}\begin{pmatrix} 3 & 0 \\ 0 & 3 \end{pmatrix} = I_2

    We check that AR = I₂ by multiplying A by R.

What it's for

It gives a matrix R that “undoes” A on the right, and it is used for systems with more unknowns than equations (rank = number of rows). R is not unique (other matrices satisfy AR = I too); this is the one the formula gives.

Proof

Particular solution: Xp = Rb

Xp=Rb  ⇒  AXp=bX_p = Rb \;\Rightarrow\; AX_p = b
  1. AR=ImAR = I_m

    We start from AR = Im (R exists because the rank is m).

  2. A(Rb)=(AR) bA(Rb) = (AR)\,b

    We prove that Xp = Rb is a solution. We compute A(Rb) and, by the associative property, it is (AR)b.

  3. (AR) b=Im b=b(AR)\,b = I_m\,b = b

    Since AR = Im, we get Imb = b. That is, A·Xp = b.

  4. Rb=13(2−111−12)(33)=13(6−33+3−3+6)=(121)Rb = \dfrac{1}{3}\begin{pmatrix} 2 & -1 \\ 1 & 1 \\ -1 & 2 \end{pmatrix}\begin{pmatrix} 3 \\ 3 \end{pmatrix} = \dfrac{1}{3}\begin{pmatrix} 6 - 3 \\ 3 + 3 \\ -3 + 6 \end{pmatrix} = \begin{pmatrix} 1 \\ 2 \\ 1 \end{pmatrix}

    Example with b = (3, 3): Rb = (1, 2, 1). The sizes: R is 3×2 and b is 2×1, so Rb is 3×1, a vector with the 3 unknowns.

  5. A(121)=(1+2+00+2+1)=(33)=bA\begin{pmatrix} 1 \\ 2 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 + 2 + 0 \\ 0 + 2 + 1 \end{pmatrix} = \begin{pmatrix} 3 \\ 3 \end{pmatrix} = b

    Check: A·(1, 2, 1) = (1 + 2 + 0, 0 + 2 + 1) = (3, 3) = b.

What it's for

It always gives a concrete (particular) solution when the rank equals the number of rows: the system is never inconsistent. It is not the only one; the others come from adding the null space to it.

Proof

Homogeneous solution: Xh = X − Rb is in the null space

AX=b  ⇒  Xh=X−Rb∈Nul⁡(A)AX = b \;\Rightarrow\; X_h = X - Rb \in \operatorname{Nul}(A)
  1. X=Rb+(X−Rb)X = Rb + (X - Rb)

    Let X be any solution of AX = b. We add and subtract Rb: X = Rb + (X − Rb). It is a trivial identity, like 5 = 3 + (5 − 3).

  2. A(X−Rb)=AX−A(Rb)A(X - Rb) = AX - A(Rb)

    Let us see what A does to the part X − Rb. By the distributive property, A(X − Rb) = AX − A(Rb).

  3. A(X−Rb)=b−(AR) b=b−I b=b−b=0A(X - Rb) = b - (AR)\,b = b - I\,b = b - b = 0

    AX = b because X is a solution, and A(Rb) = (AR)b = Ib = b. We get b − b = 0.

  4. AXh=0  ⇒  Xh∈Nul⁡(A)AX_h = 0 \;\Rightarrow\; X_h \in \operatorname{Nul}(A)

    Since A·Xh = 0, the vector Xh = X − Rb is in the null space of A. It is called a homogeneous solution because it solves AX = 0.

  5. X=(0, 3, 0):AX=(3, 3)=bX = (0,\ 3,\ 0):\quad AX = (3,\ 3) = b

    Example: X = (0, 3, 0) is another solution, because A·X = (0 + 3 + 0, 0 + 3 + 0) = (3, 3).

  6. Xh=(0, 3, 0)−(1, 2, 1)=(−1, 1, −1)∈Nul⁡(A)X_h = (0,\ 3,\ 0) - (1,\ 2,\ 1) = (-1,\ 1,\ -1) \in \operatorname{Nul}(A)

    Xh = X − Rb = (0, 3, 0) − (1, 2, 1) = (−1, 1, −1), which is in Nul(A): it is the vector t = 1 we saw earlier.

What it's for

It says that the difference between any two solutions of AX = b always lives in the null space. So, once you know the null space, you control all the solutions.

Proof

All the solutions: X = Rb + Nul(A)

AX=b  ⟺  X=Rb+Xh,Xh∈Nul⁡(A)AX = b \iff X = Rb + X_h,\quad X_h \in \operatorname{Nul}(A)
  1. AX=b  ⇒  X=Xp+XhAX = b \;\Rightarrow\; X = X_p + X_h

    We already know that every solution X can be written X = Xp + Xh, with Xp = Rb and Xh = X − Rb in the null space.

  2. A(Xp+Xh)=AXp+AXh=b+0=bA(X_p + X_h) = AX_p + AX_h = b + 0 = b

    Conversely, any Xp + Xh with Xh in the null space is a solution: A(Xp + Xh) = AXp + AXh = b + 0 = b.

  3. { X:AX=b }=Xp+Nul⁡(A)\{\, X : AX = b \,\} = X_p + \operatorname{Nul}(A)

    Conclusion: the set of all solutions is Xp plus the null space, X = Rb + Nul(A).

  4. X=(1, 2, 1)+t (−1, 1, −1)X = (1,\ 2,\ 1) + t\,(-1,\ 1,\ -1)

    In the example, Nul(A) = t(−1, 1, −1), so X = (1, 2, 1) + t(−1, 1, −1).

  5. t=0: (1, 2, 1)t=1: (0, 3, 0)t=2: (−1, 4, −1)t = 0:\ (1,\ 2,\ 1) \qquad t = 1:\ (0,\ 3,\ 0) \qquad t = 2:\ (-1,\ 4,\ -1)

    Each value of t gives a solution: t = 0 gives (1, 2, 1); t = 1, (0, 3, 0); t = 2, (−1, 4, −1). There are infinitely many.

  6. A(−14−1)=(−1+4+00+4−1)=(33)A\begin{pmatrix} -1 \\ 4 \\ -1 \end{pmatrix} = \begin{pmatrix} -1 + 4 + 0 \\ 0 + 4 - 1 \end{pmatrix} = \begin{pmatrix} 3 \\ 3 \end{pmatrix}

    We check t = 2: A·(−1, 4, −1) = (−1 + 4 + 0, 0 + 4 − 1) = (3, 3).

What it's for

It describes ALL the solutions with a single formula. Geometrically it is a line (or a plane, depending on the dimension of the null space) parallel to the null space and passing through Xp.

Proof

Left pseudoinverse: L = (AᵗA)⁻¹Aᵗ

LA=In  ⇒  L=(AtA)−1AtLA = I_n \;\Rightarrow\; L = (A^tA)^{-1}A^t
  1. L=Cn×n AtL = C_{n \times n}\,A^t

    Now we look for L (of size n×m) with LA = In. As before, we build it from Aᵗ, but on the other side: L = CAᵗ, with C an n×n matrix to be determined.

  2. LA=C (AtA)=ILA = C\,(A^tA) = I

    We substitute: LA = C·AᵗA = C(AᵗA), and we want it to equal I.

  3. C=(AtA)−1(r=n)C = (A^tA)^{-1} \qquad (r = n)

    AᵗA is n×m times m×n = n×n and, since the rank of A is n, it has an inverse (same proof with Aᵗ instead of A). Then C = (AᵗA)⁻¹.

  4. L=CAt=(AtA)−1AtL = CA^t = (A^tA)^{-1}A^t

    Back to L = CAᵗ, substituting C: L = (AᵗA)⁻¹Aᵗ.

  5. LA=(AtA)−1AtA=(AtA)−1(AtA)=ILA = (A^tA)^{-1}A^tA = (A^tA)^{-1}(A^tA) = I

    Check: LA = (AᵗA)⁻¹AᵗA = (AᵗA)⁻¹(AᵗA) = I.

  6. A=(100111):AtA=(2112),(AtA)−1=13(2−1−12)A = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{pmatrix}:\quad A^tA = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix},\quad (A^tA)^{-1} = \dfrac{1}{3}\begin{pmatrix} 2 & -1 \\ -1 & 2 \end{pmatrix}

    Example with A = (1 0; 0 1; 1 1), 3×2 with independent columns (rank 2 = n): AᵗA = (2 1; 1 2) and its inverse is (1/3)(2 −1; −1 2).

  7. L=(AtA)−1At=13(2−11−121)L = (A^tA)^{-1}A^t = \dfrac{1}{3}\begin{pmatrix} 2 & -1 & 1 \\ -1 & 2 & 1 \end{pmatrix}

    L = (AᵗA)⁻¹Aᵗ = (1/3)(2 −1 1; −1 2 1). It is a 2×3 matrix: n×m.

  8. LA=13(2−11−121)(100111)=13(3003)=I2LA = \dfrac{1}{3}\begin{pmatrix} 2 & -1 & 1 \\ -1 & 2 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{pmatrix} = \dfrac{1}{3}\begin{pmatrix} 3 & 0 \\ 0 & 3 \end{pmatrix} = I_2

    We check that LA = I₂ by multiplying L by A.

What it's for

It gives a matrix L that “undoes” A on the left, and it is used for systems with more equations than unknowns (rank = number of columns).

Proof

With L the solution is unique: X = Lb

LA=I  ⇒  (AX=b⇒X=Lb)LA = I \;\Rightarrow\; (AX = b \Rightarrow X = Lb)
  1. AX=b  ⇒  L(AX)=LbAX = b \;\Rightarrow\; L(AX) = Lb

    We start from AX = b and multiply both sides by L on the left.

  2. (LA) X=Lb(LA)\,X = Lb

    With the associative property we group: (LA)X = Lb.

  3. I X=X=LbI\,X = X = Lb

    Since LA = I, we get X = Lb: if the system has a solution, it has to be this one.

  4. AXh=0  ⇒  Xh=(LA)Xh=L(AXh)=L 0=0AX_h = 0 \;\Rightarrow\; X_h = (LA)X_h = L(AX_h) = L\,0 = 0

    Uniqueness: if Xh is in the null space (AXh = 0), then Xh = (LA)Xh = L(AXh) = L·0 = 0. The only vector in the null space is 0.

  5. Nul⁡(A)={0}(dim⁡=n−r=0)\operatorname{Nul}(A) = \{0\} \qquad (\dim = n - r = 0)

    It agrees with the rank-nullity theorem: dim Nul(A) = n − r = 0 when r = n.

  6. A=(100111), b=(123):X=Lb=13(2−11−121)(123)=(12)A = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{pmatrix},\ b = \begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix}:\quad X = Lb = \dfrac{1}{3}\begin{pmatrix} 2 & -1 & 1 \\ -1 & 2 & 1 \end{pmatrix}\begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix} = \begin{pmatrix} 1 \\ 2 \end{pmatrix}

    Example with A = (1 0; 0 1; 1 1) and b = (1, 2, 3): Lb = (1/3)(2 − 2 + 3, −1 + 4 + 3) = (1, 2).

  7. A(12)=(123)=bA\begin{pmatrix} 1 \\ 2 \end{pmatrix} = \begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix} = b

    We check: A·(1, 2) = (1, 2, 1 + 2) = (1, 2, 3) = b.

What it's for

With more equations than unknowns and full column rank, there is at most one solution and L finds it. But Lb is only the candidate: you must check that it really solves the system (next demonstration).

Proof

Lb is a solution if and only if b is in Col(A)

A(Lb)=b  ⟺  b∈Col⁡(A)A(Lb) = b \iff b \in \operatorname{Col}(A)
  1. Col⁡(A)={ AX }={ x1a1+⋯+xnan }\operatorname{Col}(A) = \{\, AX \,\} = \{\, x_1 a_1 + \cdots + x_n a_n \,\}

    Col(A) (the column space, or image) is the set of all vectors you can form by combining the columns of A: AX = x₁a₁ + ⋯ + xnan, where a₁, …, an are the columns.

  2. A(Lb)=b  ⇒  b=A (Lb)∈Col⁡(A)A(Lb) = b \;\Rightarrow\; b = A\,(Lb) \in \operatorname{Col}(A)

    If Lb is a solution, then b = A(Lb) has the form AX, so b is in Col(A).

  3. b=AX0  ⇒  Lb=LAX0=X0  ⇒  A(Lb)=AX0=bb = AX_0 \;\Rightarrow\; Lb = LAX_0 = X_0 \;\Rightarrow\; A(Lb) = AX_0 = b

    Conversely, if b is in Col(A), b = AX₀ for some X₀. Then Lb = LAX₀ = X₀, and A(Lb) = AX₀ = b: Lb is indeed a solution.

  4. A=(100111):Col⁡(A)={ x1(1,0,1)+x2(0,1,1) }={ (x1, x2, x1+x2) }A = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{pmatrix}:\quad \operatorname{Col}(A) = \{\, x_1(1, 0, 1) + x_2(0, 1, 1) \,\} = \{\, (x_1,\ x_2,\ x_1 + x_2) \,\}

    For A = (1 0; 0 1; 1 1) the columns are (1, 0, 1) and (0, 1, 1). Combining them gives (x₁, x₂, x₁ + x₂): the vectors whose third entry is the sum of the first two (a plane in ℝ³).

  5. b=(1, 2, 3):1+2=3  ⇒  b∈Col⁡(A),A(Lb)=A(1,2)=bb = (1,\ 2,\ 3):\quad 1 + 2 = 3 \;\Rightarrow\; b \in \operatorname{Col}(A),\quad A(Lb) = A(1, 2) = b

    b = (1, 2, 3): 1 + 2 = 3, so b is in Col(A), and A(Lb) = A(1, 2) = b. There is a solution, and it is unique.

  6. b′=(1, 2, 0):Lb′=(0, 1),A(Lb′)=(0, 1, 1)≠b′b' = (1,\ 2,\ 0):\quad Lb' = (0,\ 1),\quad A(Lb') = (0,\ 1,\ 1) \neq b'

    b′ = (1, 2, 0): 1 + 2 ≠ 0, it is not in Col(A). Lb′ = (0, 1), but A(Lb′) = (0, 1, 1) ≠ b′: Lb′ is NOT a solution. The equations x₁ = 1, x₂ = 2 and x₁ + x₂ = 0 contradict each other.

What it's for

It is the practical test: compute Lb and check that A(Lb) = b. If it holds, that is the only solution; if not, the system has none (least squares, later on, looks for the best approximation).

Proof

If A is square and regular, R = L = A⁻¹

r=m=n  ⇒  R=L=A−1r = m = n \;\Rightarrow\; R = L = A^{-1}
  1. (AAt)−1=(At)−1A−1(AA^t)^{-1} = (A^t)^{-1}A^{-1}

    If A is square of rank n, R and L exist, and A and Aᵗ have an inverse. We use (AB)⁻¹ = B⁻¹A⁻¹ on AAᵗ: (AAᵗ)⁻¹ = (Aᵗ)⁻¹A⁻¹.

  2. R=At(AAt)−1=At(At)−1A−1=I A−1=A−1R = A^t(AA^t)^{-1} = A^t(A^t)^{-1}A^{-1} = I\,A^{-1} = A^{-1}

    We substitute into R: R = Aᵗ(Aᵗ)⁻¹A⁻¹ = I·A⁻¹ = A⁻¹.

  3. (AtA)−1=A−1(At)−1(A^tA)^{-1} = A^{-1}(A^t)^{-1}

    For L: (AᵗA)⁻¹ = A⁻¹(Aᵗ)⁻¹, with the same reasoning.

  4. L=(AtA)−1At=A−1(At)−1At=A−1 I=A−1L = (A^tA)^{-1}A^t = A^{-1}(A^t)^{-1}A^t = A^{-1}\,I = A^{-1}

    L = A⁻¹(Aᵗ)⁻¹Aᵗ = A⁻¹·I = A⁻¹.

  5. A=(2111):AAt=(5332),(AAt)−1=(2−3−35)A = \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}:\quad AA^t = \begin{pmatrix} 5 & 3 \\ 3 & 2 \end{pmatrix},\quad (AA^t)^{-1} = \begin{pmatrix} 2 & -3 \\ -3 & 5 \end{pmatrix}

    Example with A = (2 1; 1 1): AAᵗ = (5 3; 3 2), with det = 10 − 9 = 1, and (AAᵗ)⁻¹ = (2 −3; −3 5).

  6. R=At(AAt)−1=(2111)(2−3−35)=(1−1−12)=A−1R = A^t(AA^t)^{-1} = \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}\begin{pmatrix} 2 & -3 \\ -3 & 5 \end{pmatrix} = \begin{pmatrix} 1 & -1 \\ -1 & 2 \end{pmatrix} = A^{-1}

    R = Aᵗ(AAᵗ)⁻¹ = (2 1; 1 1)(2 −3; −3 5) = (1 −1; −1 2), which is exactly A⁻¹.

What it's for

It ties the cases together: the everyday inverse is the case where R and L coincide. With A square and regular, the solution X = A⁻¹b is unique and always exists.

Ți-a fost util?

Acest ghid este gratuit și fără reclame. Dacă te ajută la învățat, poți să-mi cumperi o cafea.

Cumpără-mi o cafea