View source for Topics in Abstract Algebra/Linear algebra

== The Moore-Penrose inverse ==
Inverse matrices play a key role in linear algebra, and particularly in computations. However, only square matrices can possibly be invertible. 
This leads us to introduce the ''Moore-Penrose inverse'' of a potentially non-square real- or complex-valued matrix, which satisfies some but not necessarily all of the properties of an inverse matrix.  

{{Topics in Abstract Algebra/Theorem|theorem=Definition|claim=
Let <math>A</math> be an ''m''-by-''n'' matrix over a field <math>\mathbb{K}</math> and <math>A^+</math> be an ''n''-by-''m'' matrix over <math>\mathbb{K}</math>, where <math>\mathbb{K}</math> is either <math>\mathbb{R}</math>, the real numbers, or <math>\mathbb{C}</math>, the complex numbers. Recall that <math>A^*</math> refers to the conjugate transpose of <math>A</math>. Then the following four criteria are called the ''Moore–Penrose conditions for <math>A</math>'':
# <math>AA^+A = A</math>,
# <math>A^+AA^+ = A^+</math>,
# <math>\left(AA^+\right)^* = AA^+</math>,
# <math>\left(A^+A\right)^* = A^+A</math>.
}}

We will see below that given a matrix <math>A</math>, there exists a unique matrix <math>A^+</math> that satisfies all four of the Moore–Penrose conditions. They generalise the properties of the usual inverse.

{{Topics in Abstract Algebra/Theorem|theorem=Remark|claim=
If <math>A</math> is an invertible square matrix, then the ordinary inverse <math>A^{-1}</math> satisfies the Moore-Penrose conditions for <math>A</math>. Observe also that if <math>A^+</math>  satisfies the Moore-Penrose conditions for <math>A</math>, then <math>A</math> satisfies the Moore-Penrose conditions for <math>A^+</math>. }}

=== Basic properties of the Hermitian conjugate ===
We assemble some basic properties of the conjugate transpose for later use. In the following lemmas, <math>A</math> is a matrix with complex elements and ''n'' columns, <math>B</math> is a matrix with complex elements and ''n'' rows.

{{Topics in Abstract Algebra/Theorem|theorem=Lemma|name=1|claim=For any <math>\mathbb{K}</math>-matrix <math>A</math>, <math>A^* A = 0 \Rightarrow A = 0</math>|proof=

The assumption says that all elements of ''A*A'' are zero. Therefore,
: <math>0 =
  \operatorname{Tr}\left(A^*A\right) =
  \sum_{j=1}^n \left(A^*A\right)_{jj} =
  \sum_{j=1}^n \sum_{i=1}^m \left(A^*\right)_{ji}A_{ij} =
  \sum_{i=1}^m \sum_{j=1}^n \left|A_{ij}\right|^2
.</math>

Therefore, all <math>A_{ij}</math> equal 0 i.e. <math>A = 0</math>.}}

{{Topics in Abstract Algebra/Theorem|theorem=Lemma|name=2|claim=For any <math>\mathbb{K}</math>-matrix <math>A</math>, <math>A^* A B = 0 \Rightarrow AB = 0</math>|proof=

: <math>\begin{align}
              0 &= A^*AB      & \\
  \Rightarrow 0 &= B^*A^*AB   & \\
  \Rightarrow 0 &= (AB)^*(AB) & \\
  \Rightarrow 0 &= AB         &(\text{by Lemma 1})
\end{align}</math>}}

{{Topics in Abstract Algebra/Theorem|theorem=Lemma|name=3|claim=For any <math>\mathbb{K}</math>-matrix <math>A</math>, <math>A B B^* = 0 \Rightarrow AB = 0</math>|proof=

This is proved in a manner similar to the argument of Lemma 2 (or by simply taking the Hermitian conjugate).}}

=== Existence and uniqueness ===
We establish existence and uniqueness of the Moore-Penrose inverse for every matrix.

{{Topics in Abstract Algebra/Theorem|theorem=Theorem|name=|claim=If <math>A</math> is a <math>\mathbb{K}</math>-matrix and  <math>A^+_1</math> and <math>A^+_2</math>  satisfy the Moore-Penrose conditions for <math>A</math>, then <math>A^+_1 = A^+_2</math>.|proof=Let <math>A</math> be a matrix over <math>\mathbb{R}</math> or <math>\mathbb{C}</math>. Suppose that <math>{A^+_1}</math> and <math>{A^+_2}</math> are Moore–Penrose inverses of <math>A</math>. Observe then that
: <math>A{A^+_1}
\overset{(1)}{{}={}}
(A{A^+_2}A){A^+_1} = (A{A^+_2})(A{A^+_1})
\overset{(3)}{{}={}}
(A{A^+_2})^*(A{A^+_1})^* = {A^+_2}^*(A{A^+_1}A)^*
\overset{(1)}{{}={}}
{A^+_2}^*A^* = (A{A^+_2})^*
\overset{(3)}{{}={}}
A{A^+_2}.</math>

Analogously we conclude that <math>{A^+_1}A = {A^+_2}A</math>. The proof is completed by observing that then
: <math>{A^+_1}
\overset{(2)}{{}={}}
{A^+_1}A{A^+_1} = {A^+_1}A{A^+_2}
= A^+_2A{A^+_2}
\overset{(2)}{{}={}}
{A^+_2}.</math>}}


{{Topics in Abstract Algebra/Theorem|theorem=Theorem|claim=For every <math>\mathbb{K}</math>-matrix <math>A</math> there is a matrix <math>A^+</math> satisfying the Moore-Penrose conditions for <math>A</math>
|proof=The proof proceeds in stages.  

'''<math>A</math> is a 1-by-1 matrix'''

For any <math>x \in \mathbb{K}</math>, we define:
: <math>x^+ := \begin{cases}
    x^{-1},  & \mbox{if }x \neq 0 \\
    0,       & \mbox{if }x = 0
  \end{cases}
</math>

It is easy to see that <math>x^+</math> is a pseudoinverse of <math>x</math> (interpreted as a 1-by-1 matrix).

'''<math>A</math> is a square diagonal matrix'''

Let <math>D</math> be an ''n''-by-''n'' matrix over <math>\mathbb{K}</math> with zeros off the diagonal. We define <math>D^+</math> as an ''n''-by-''n'' matrix over <math>\mathbb{K}</math> with <math>\left(D^+\right)_{ij} := \left(D_{ij}\right)^+</math> as defined above. We write simply <math>D^+_{ij}</math> for <math>\left(D^+\right)_{ij} = \left(D_{ij}\right)^+</math>.

Notice that <math>D^+</math> is also a matrix with zeros off the diagonal.

We now show that <math>D^+</math> is a pseudoinverse of <math>D</math>:
# <math>\left(DD^+D\right)_{ij} = D_{ij}D^+_{ij}D_{ij} = D_{ij} \Rightarrow DD^+D = D</math>
# <math>\left(D^+DD^+\right)_{ij} = D^+_{ij}D_{ij}D^+_{ij} = D^+_{ij} \Rightarrow D^+DD^+ = D^+</math>
# <math>\left(DD^+\right)^*_{ij} = \overline{\left(DD^+\right)_{ji}} = \overline{D_{ji}D^+_{ji}} = \left(D_{ji}D^+_{ji}\right)^* = D_{ji}D^+_{ji} = D_{ij}D^+_{ij} \Rightarrow \left(DD^+\right)^* = DD^+</math>
# <math>\left(D^+D\right)^*_{ij} = \overline{\left(D^+D\right)_{ji}} = \overline{D^+_{ji}D_{ji}} = \left(D^+_{ji}D_{ji}\right)^* = D^+_{ji}D_{ji} = D^+_{ij}D_{ij} \Rightarrow \left(D^+D\right)^* = D^+D</math>  

'''<math>A</math> is a general diagonal matrix'''

Let <math>D</math> be an ''m''-by-''n'' matrix over <math>\mathbb{K}</math> with zeros off the main diagonal, where ''m'' and ''n'' are unequal. That is, <math>D_{ij} = d_{i}</math> for some <math>d_{i}\in\mathbb{K}</math> when <math>i = j</math> and <math>D_{ij} = 0</math> otherwise.

Consider the case where <math>n>m</math>. Then we can rewrite <math>D = \left[D_0\,\,\mathbf{0}_{m\times (n-m)}\right]</math> by stacking where <math>D_0</math> is a square diagonal ''m''-by-''m'' matrix, and <math>\mathbf{0}_{m\times(n-m)}</math> is the ''m''-by-(''n''−''m'') zero matrix. We define <math>D^+ \equiv \begin{bmatrix}
    D_0^+ \\
    \mathbf{0}_{(n-m)\times m}
  \end{bmatrix}
</math> as an ''n''-by-''m'' matrix over <math>\mathbb{K}</math>, with <math>D_0^+</math> the pseudoinverse of <math>D_0</math> defined above, and <math>\mathbf{0}_{(n-m)\times m}</math> the (''n''−''m'')-by-''m'' [[zero matrix]]. We now show that <math>D^+</math> is a pseudoinverse of <math>D</math>:
# By multiplication of block matrices, <math>DD^+ = D_0D_0^+ + \mathbf{0}_{m\times(n-m)}\mathbf{0}_{(n-m)\times m} = D_0D_0^+,</math> so by property 1 for square diagonal matrices <math>D_0</math> proven in the previous section,<math>
  DD^+D = D_0D_0^+\left[D_0\,\,\mathbf{0}_{m\times (n-m)}\right] =
          \left[D_0D_0^+D_0\,\,\mathbf{0}_{m\times (n-m)}\right] =
          \left[D_0\,\,\mathbf{0}_{m\times (n-m)}\right] =
          D
</math>.
# Similarly, <math>D^+D = \begin{bmatrix}
    D_0^+D_0 & \mathbf{0}_{m\times(n-m)} \\
    \mathbf{0}_{(n-m)\times m} & \mathbf{0}_{(n-m)\times(n-m)}
  \end{bmatrix}</math>, so <math>D^+DD^+ = \begin{bmatrix}
    D_0^+D_0 & \mathbf{0}_{m\times(n-m)} \\
    \mathbf{0}_{(n-m)\times m} & \mathbf{0}_{(n-m)\times(n-m)}
  \end{bmatrix}\begin{bmatrix}
    D_0^+ \\
    \mathbf{0}_{(n-m)\times m}
  \end{bmatrix} = \begin{bmatrix}
    D_0^+D_0D_0^+ \\
    \mathbf{0}_{(n-m)\times m}
  \end{bmatrix} = D^+.
</math>
# By 1 and property 3 for square diagonal matrices, <math>\left(DD^+\right)^* = \left(D_0D_0^+\right)^* = D_0D_0^+ = DD^+</math>.
# By 2 and property 4 for square diagonal matrices, <math>\left(D^+D\right)^* = \begin{bmatrix}
    \left(D_0^+D_0\right)^* & \mathbf{0}_{m\times(n-m)} \\
    \mathbf{0}_{(n-m)\times m} & \mathbf{0}_{(n-m)\times(n-m)}
  \end{bmatrix} = \begin{bmatrix}
    D_0^+D_0 & \mathbf{0}_{m\times(n-m)} \\
    \mathbf{0}_{(n-m)\times m} & \mathbf{0}_{(n-m)\times(n-m)}
  \end{bmatrix} = D^+D.
</math>

Existence for <math>D</math> such that <math>m > n</math> follows by swapping the roles of <math>D</math> and <math>D^+</math> in the <math>n > m</math> case and using the fact that <math>\left(D^+\right)^+ = D</math>.

'''<math>A</math> is an arbitrary matrix'''

The singular value decomposition theorem states that there exists a factorization of the form
: <math>A = U\Sigma V^*</math>

where:
: <math>U</math> is an ''m''-by-''m'' unitary matrix over <math>\mathbb{K}</math>.
: <math>\Sigma</math> is an ''m''-by-''n'' matrix over <math>\mathbb{K}</math> with nonnegative real numbers on the diagonal and zeros off the diagonal.
: <math>V</math> is an ''n''-by-''n'' unitary matrix over <math>\mathbb{K}</math>.<ref>Some authors use slightly different dimensions for the factors. The two definitions are equivalent.</ref>

Define <math>A^+</math> as <math>V\Sigma^+U^*</math>.

We now show that <math>A^+</math> is a pseudoinverse of <math>A</math>:

# <math>AA^+A = U\Sigma V^*V\Sigma^+U^*U\Sigma V^* = U\Sigma\Sigma^+\Sigma V^* = U\Sigma V^* = A</math>
# <math>A^+AA^+ = V\Sigma^+U^*U\Sigma V^*V\Sigma^+U^* = V\Sigma^+\Sigma\Sigma^+U^* = V\Sigma^+U^* = A^+</math>
# <math>\left(AA^+\right)^* = \left(U\Sigma V^*V\Sigma^+U^*\right)^* = \left(U\Sigma\Sigma^+U^*\right)^* = U\left(\Sigma\Sigma^+\right)^*U^* = U\left(\Sigma\Sigma^+\right)U^* = U\Sigma V^*V\Sigma^+U^* = AA^+</math>
# <math>\left(A^+A\right)^* = \left(V\Sigma^+U^*U\Sigma V^*\right)^* = \left(V\Sigma^+\Sigma V^*\right)^* = V\left(\Sigma^+\Sigma\right)^*V^* = V\left(\Sigma^+\Sigma\right)V^* = V\Sigma^+U^*U\Sigma V^* = A^+A</math>
}}

This leads us to the natural definition:

{{Topics in Abstract Algebra/Theorem|theorem=Definition|name=Moore-Penrose inverse|claim=Let <math>A</math> be a <math>\mathbb{K}</math>-matrix. Then the unique <math>\mathbb{K}</math>-matrix satisfying the Moore-Penrose conditions for <math>A</math> is called the ''Moore-Penrose inverse'' <math>A^+</math> of <math>A</math>.}}

===Basic properties===
We have already seen above that the Moore-Penrose inverse generalises the classical inverse to potentially non-square matrices.
We will now list some basic properties of its interaction with the Hermitian conjugate, leaving most of the proofs as exercises to the reader.

{{Topics in Abstract Algebra/Theorem|theorem=Exercise|claim=For any <math>\mathbb{K}</math>-matrix <math>A</math>, <math>{A^*}^+ = {A^+}^*</math>}}

The following identities hold:
# ''A''<sup>+</sup> = ''A''<sup>+</sup> ''A''<sup>+*</sup> ''A''{{sup|*}}
# ''A''<sup>+</sup> = ''A''{{sup|*}} ''A''<sup>+*</sup> ''A''<sup>+</sup>
# ''A'' = ''A''<sup>+*</sup> ''A''{{sup|*}} ''A''
# ''A'' = ''A A''{{sup|*}} ''A''<sup>+*</sup>
# ''A''{{sup|*}} = ''A''{{sup|*}} ''A A''<sup>+</sup>
# ''A''{{sup|*}} = ''A''<sup>+</sup> ''A A''{{sup|*}}

''Proof'' of the first one: <math>A^+ = A^+AA^+</math> and <math>AA^+ = \left(AA^+\right)^*</math> imply that <math>A^+ = A^+\left(A A^+\right)^* = A^+A^{+^*}A^*</math>. □

The remaining identities are left as ''exercises''.

=== Reduction to the Hermitian case ===
The results of this section show that the computation of the pseudoinverse is reducible to its construction in the
Hermitian case. It suffices to show that the putative constructions satisfy the defining criteria.

{{Topics in Abstract Algebra/Theorem|theorem=Proposition|claim=For every <math>\mathbb{K}</math>-matrix <math>A</math>, <math>A^+ = A^* (A A^*)^+</math>|proof=
Observe that

: <math>\begin{align}
  &                & AA^* &= AA^*\left(AA^*\right)^+ AA^* & \\
  &\Leftrightarrow & AA^* &= ADAA^*                       & \\
  &\Leftrightarrow &    0 &= (AD - I)AA^*                 & \\
  &\Leftrightarrow &    0 &= ADA - A                      & (\text{by Lemma 3}) \\
  &\Leftrightarrow &    A &= ADA                          &
\end{align}</math>

Similarly, <math>\left(AA^*\right)^+AA^*\left(AA^*\right)^+ = \left(AA^*\right)^+</math> implies that <math>A^*\left(AA^*\right)^+AA^*\left(AA^*\right)^+ = A^*\left(AA^*\right)^+</math> i.e. <math>DAD = D</math>.

Additionally, <math>AD = AA^*\left(AA^*\right)^+</math> so <math>AD = (AD)^*</math>.

Finally, <math>DA = A^*\left(AA^*\right)^+A</math> implies that <math>(DA)^* = A^* \left(\left(AA^*\right)^+\right)^*A = A^* \left(\left(AA^*\right)^+\right)A = DA</math>.

Therefore, <math>D = A^+</math>.}}

{{Topics in Abstract Algebra/Theorem|theorem=Exercise|claim=For every <math>\mathbb{K}</math>-matrix <math>A</math>, <math>A^+ = (A^* A)^+ A^*</math>}}

=== Products ===
We now turn to calculating the Moore-Penrose inverse for a product of two matrices,  <math>C = AB.</math>

{{Topics in Abstract Algebra/Theorem|theorem=Proposition|claim=If <math>A</math> has orthonormal columns i.e. <math>A^*A = I</math>, then for any <math>\mathbb{K}</math>-matrix <math>B</math> of the right dimensions, <math>(AB)^+ = B^+ A^+</math>.|proof=
Since <math>A^*A = I</math>, <math>A^+ = A^*</math>. Write <math>C = AB</math> and <math>D = B^+A^+ = B^+A^*</math>. We show that <math>D</math> satisfies the Moore–Penrose criteria for <math>C</math>.

: <math>\begin{align}
     CDC &= ABB^+A^*AB = ABB^+B = AB = C, \\[4pt]
     DCD &= B^+A^*ABB^+A^* = B^+BB^+A^* = B^+A^* = D, \\[4pt]
  (CD)^* &= D^*B^*A^* = A\left(B^+\right)^*B^*A^* = A\left(BB^+\right)^*A^* = ABB^+A^* = CD, \\[4pt]
  (DC)^* &= B^*A^*D^* = B^*A^*A\left(B^+\right)^* = \left(B^+B\right)^* = B^+B = B^+A^*AB = DC .
\end{align}</math>

Therefore, <math>D = C^+</math>.}}

{{Topics in Abstract Algebra/Theorem|theorem=Exercise|claim=If <math>B</math> has orthonormal rows, then for any <math>\mathbb{K}</math>-matrix <math>A</math> of the right dimensions, <math>(AB)^+ = B^+ A^+</math>.}}

Another important special case which approximates closely that of invertible matrices is when <math>A</math> has full column rank and <math>B</math> has full row rank.

{{Topics in Abstract Algebra/Theorem|theorem=Proposition|claim=If <math>A</math> has full column rank and <math>B</math> has full row rank, then <math>(AB)^+ = B^+ A^+</math>.|proof=
Since <math>A</math> has full column rank, <math>A^*A</math> is invertible so <math>\left(A^*A\right)^+ = \left(A^*A\right)^{-1}</math>. Similarly, since <math>B</math> has full row rank, <math>BB^*</math> is invertible so <math>\left(BB^*\right)^+ = \left(BB^*\right)^{-1}</math>.

Write <math>D = B^+A^+ = B^*\left(BB^*\right)^{-1}\left(A^*A\right)^{-1}A^*</math>(using reduction to the Hermitian case). We show that <math>D</math> satisfies the Moore–Penrose criteria.

: <math>\begin{align}
                  CDC &= ABB^*\left(BB^*\right)^{-1}\left(A^*A\right)^{-1}A^*AB = AB = C, \\[4pt]
                  DCD &= B^*\left(BB^*\right)^{-1}\left(A^*A\right)^{-1}A^*ABB^*\left(BB^*\right)^{-1}\left(A^*A\right)^{-1}A^* = B^*\left(BB^*\right)^{-1}\left(A^*A\right)^{-1}A^* = D, \\[4pt]
                   CD &= ABB^*\left(BB^*\right)^{-1}\left(A^*A\right)^{-1}A^* = A\left(A^*A\right)^{-1}A^* = \left(A\left(A^*A\right)^{-1}A^*\right)^*, \\
   \Rightarrow (CD)^* &= CD, \\[4pt]
                   DC &= B^*\left(BB^*\right)^{-1}\left(A^*A\right)^{-1}A^*AB = B^*\left(BB^*\right)^{-1}B = \left(B^*\left(BB^*\right)^{-1}B\right)^*, \\
   \Rightarrow (DC)^* &= DC.
\end{align}</math>

Therefore, <math>D = C^+</math>.}}

We finally derive a formula for calculating the Moore-Penrose inverse of <math>A A^*</math>.

{{Topics in Abstract Algebra/Theorem|theorem=Proposition|claim=If <math>B = A^*</math>, then <math>(AB)^+ = A^{+*} A^+</math>.|proof=
Here, <math>B = A^*</math>, and thus <math>C = AA^*</math> and <math>D = A^{+*} A^+</math>. We show that indeed <math>D</math> satisfies the four Moore–Penrose criteria.
: <math>\begin{align}
     CDC &= A A^* A^{+*} A^+ A A^* = A \left(A^+A\right)^*A^+A A^* = A A^+A A^+A A^* = A A^+A A^* = A A^* = C \\[4pt]
     DCD &= A^{+*} A^+ A A^* A^{+*} A^+ = A^{+*} A^+ A \left(A^+A\right)^*A^+ = A^{+*} A^+ A A^+A A^+ = A^{+*} A^+ A A^+ = A^{+*} A^+ = D \\[4pt]
  (CD)^* &= \left(A A^* A^{+*} A^+\right)^* = A^{+*} A^+ A A^* = A^{+*} \left(A^+ A\right)^* A^* = A^{+*} A^* A^{+*} A^* \\
         &= \left(A A^+\right)^* \left(A A^+\right)^* = A A^+ A A^+ = A\left(A^+A\right)^*A^+ = A A^*A^{+*} A^+ = CD \\[4pt]
  (DC)^* &= \left(A^{+*} A^+ A A^*\right)^* = A A^* A^{+*} A^+ = A \left(A^+ A\right)^* A^+ = A A^+ A A^+ \\
         &= \left(A A^+\right)^* \left(A A^+\right)^* = A^{+*} A^* A^{+*} A^* = A^{+*} \left(A^+ A\right)^* A^* = A^{+*} A^+ A A^* = DC
\end{align}</math>

Therefore, <math>D = C^+</math>. In other words:
: <math>\left(A A^*\right)^+ = A^{+*} A^+</math>

and, since <math>\left(A^*\right)^* = A</math>
: <math>\left(A^*A\right)^+ = A^+A^{+*}</math>}}

=== Projectors and subspaces ===
The defining feature of classical inverses is that <math>A A^{-1} = A^{-1} A = I.</math> What can we say about <math>A A^+</math> and <math>A^+ A</math>? 

We can derive some properties easily from the more basic properties above:

{{Topics in Abstract Algebra/Theorem|theorem=Exercise|claim=Let <math>A</math> be a <math>\mathbb{K}</math>-matrix. Then <math>(A A^+)^2=(A A^+), (A^+ A)^2=(A^+ A),(A A^+)^*=(A A^+)</math> and <math>(A^+ A)^*=(A^+ A)</math>}}

We can conclude that <math>P = AA^+</math> and <math>Q = A^+ A</math> are orthogonal projections.

{{Topics in Abstract Algebra/Theorem|theorem=Proposition|claim=Let <math>A</math> be a <math>\mathbb{K}</math>-matrix. Then <math>P = AA^+</math> and <math>Q = A^+ A</math> are orthogonal projections|proof=

Indeed, consider the operator <math>P</math>: any vector decomposes as

: <math>x = Px + (I - P)x</math>

and for all vectors <math>x</math> and <math>y</math> satisfying <math>Px = x</math> and <math>(I - P)y = y</math>, we have

: <math>x^*y = (Px)^*(I - P)y = x^* P^*(I - P)y = x^*P(I - P)y = 0</math>.

It follows that <math>PA = AA^+ A = A</math> and <math>A^+ P = A^+ AA^+ = A^+</math>. Similarly, <math>QA^+ = A^+</math> and <math>AQ = A</math>. The orthogonal components are now readily identified.}}

We finish our analysis by determining image and kernel of the mappings encoded by the Moore-Penrose inverse.

{{Topics in Abstract Algebra/Theorem|theorem=Proposition|claim=Let <math>A</math> be a <math>\mathbb{K}</math>-matrix. Then <math>\operatorname{Ker}\left(A^+\right) = \operatorname{Ker}\left(A^*\right)</math> and <math>\operatorname{Im}\left(A^+\right) = \operatorname{Im}\left(A^*\right)</math>.|proof=

If <math>y</math> belongs to the range of <math>A</math> then for some <math>x</math>, <math>y = Ax</math> and <math>Py = PAx = Ax = y</math>. Conversely, if <math>Py = y</math> then <math>y = AA^+ y</math> so that <math>y</math> belongs to the range of <math>A</math>. It follows that <math>P</math> is the orthogonal projector onto the range of <math>A</math>. <math>I - P</math> is then the orthogonal projector onto the orthogonal complement of the range of <math>A</math>, which equals the kernel of <math>A^*</math>.

A similar argument using the relation <math>QA^* = A^*</math> establishes that <math>Q</math> is
the orthogonal projector onto the range of <math>A^*</math> and <math>(I - Q)</math> is the orthogonal projector onto the kernel of <math>A</math>.

Using the relations <math>P\left(A^+\right)^* = P^*\left(A^+\right)^* = \left(A^+ P\right)^* = \left(A^+\right)^*</math> and <math>P = P^* = \left(A^+\right)^* A^*</math> it follows that the range of ''P'' equals the range of <math>\left(A^+\right)^*</math>, which in turn implies that the range of <math>I - P</math> equals the kernel of <math>A^+</math>. Similarly <math>QA^+ = A^+</math> implies that the range of <math>Q</math> equals the range of <math>A^+</math>.  Therefore, we find,

:<math>\begin{align}
  \operatorname{Ker}\left(A^+\right) &= \operatorname{Ker}\left(A^*\right). \\
   \operatorname{Im}\left(A^+\right) &= \operatorname{Im}\left(A^*\right). \\
\end{align}</math>
}}

===Applications===
We present two applications of the Moore-Penrose inverse in solving linear systems of equations.
====Least-squares minimization====
Moore-Penrose inverses can be used for least-squares minimisation of a system of equations that might not necessarily have an exact solution.

{{Topics in Abstract Algebra/Theorem|theorem=Proposition|claim=For any <math>m \times n</math> matrix <math>A</math>, <math>\|Ax -b\|_2 \ge \|Az -b\|_2</math> where <math>z = A^+ b</math>.|proof=

We first note that (stating the complex case), using the fact that
<math>P = A A^+ </math> satisfies <math> PA = A </math> and <math> P = P^* </math>, we have
:<math>
\begin{alignat}{2}
A^*(Az - b) & = A^*(A A^+ b - b)\\
& = A^*(P b - b) \\
& = A^*P^* b - A^*b  \\
& = (PA)^* b - A^*b  \\
& = 0
\end{alignat}
</math>
so that (<math>\text{c.c.}</math> stands for the Hermitian conjugate of the previous term in the following)
:<math>
\begin{alignat}{2}
\|Ax -b\|_2^2 &= \|Az -b\|_2^2 + (A(x-z))^*(Az-b) + \text{c.c.} + \|A(x - z)\|_2^2 \\
&= \|Az -b\|_2^2 + (x-z)^*A^*(Az-b) + \text{c.c.} + \|A(x - z)\|_2^2 \\
&= \|Az -b\|_2^2 + \|A(x - z)\|_2^2\\
& \ge \|Az -b\|_2^2
\end{alignat}
</math>
as claimed.
}}

{{Topics in Abstract Algebra/Theorem|theorem=Remark|claim=This lower bound need not be zero as the system <math>Ax=b</math> may not have a solution (e.g. when the matrix ''A'' does not have full rank or the system is overdetermined). 
If <math>A</math> is injective i.e. one-to-one (which implies <math> m \ge n </math>), then the bound is attained uniquely at <math>z</math>.}}

====Minimum-norm solution to a linear system====
The proof above also shows that if the system <math>Ax = b</math> is satisfiable i.e. has a solution, then necessarily <math>z = A^+b</math> is a solution (not necessarily unique). We can say more:

{{Topics in Abstract Algebra/Theorem|theorem=Proposition|claim=If the system <math>Ax = b</math> is satisfiable, then <math>z = A^+b</math> is the unique solution with smallest Euclidean norm.|proof=

Note first, with <math>Q = A^+ A</math>, that <math>Qz = A^+ AA^+ b = A^+ b = z</math> and that <math>Q^* = Q</math>. Therefore, assuming that <math>Ax = b</math>, we have
:<math>\begin{align}
  z^*(x - z) &= (Qz)^*(x - z) \\
             &= z^*Q(x - z) \\
             &= z^*\left(A^+ Ax - z\right) \\
             &= z^*\left(A^+ b - z\right) \\
             &= 0.
\end{align}</math>

Thus
:<math>\begin{alignat}{2}
  \|x\|_2^2 &= \| z + (x - z) \|_2^2 \\
            &= \|z\|_2^2 + z^*(x - z) + \overline{z^*(x - z)} + \|x - z\|_2^2 \\
            &= \|z\|_2^2 + \|x - z\|_2^2 \\
            &\ge \|z\|_2^2
\end{alignat}</math>

with equality if and only if <math>x = z</math>, as was to be shown. }}

An immediate consequence of this result is that <math>z</math> is also the uniquely smallest solution to the least-squares minimization problem for all <math>Ax = b</math>, including when <math> A </math> is neither injective nor surjective. It can be shown that the least-squares approximation <math>Az = y \approx b</math> is unique. Thus it is necessary and sufficient for all <math>x</math> that solve the least-squares minimization to satisfy <math>Ax = y = Az = AA^+b</math>. This system always has a solution (not necessarily unique) as <math>Az</math> lies in the column space of <math>A</math>. From the above result the smallest <math>x</math> which solves this system is <math>A^+(AA^+b) = A^+b = z</math>.

==Notes==
{{Reflist}}

==References==
* {{cite book | first1 = Adi | last1 = Ben-Israel | first2 = Thomas N.E. | last2 = Greville | title = Generalized inverses: Theory and applications | edition = 2nd | location = New York, NY | publisher = Springer | year = 2003 | isbn = 978-0-387-00293-4 | doi = 10.1007/b97366 }}
* {{cite book| first1 = S. L. | last1 = Campbell | first2 = C. D. | last2 = Meyer, Jr. | title= Generalized Inverses of Linear Transformations| url = https://archive.org/details/generalizedinver0000camp | url-access = registration |
publisher=Dover |year=1991 | isbn = 978-0-486-66693-8 }}
* {{cite book| first = Yoshihiko | last = Nakamura  | title= Advanced Robotics: Redundancy and Optimization|
publisher=Addison-Wesley  |year= 1991 | isbn = 978-0201151985 }}
* {{cite book| first1 = C. Radhakrishna | last1 = Rao | first2 = Sujit Kumar | last2 = Mitra| title = Generalized Inverse of Matrices and its Applications | url = https://archive.org/details/generalizedinver0000raoc | url-access = registration | publisher= John Wiley & Sons |location = New York |year= 1971 | pages=[https://archive.org/details/generalizedinver0000raoc/page/240 240] | isbn = 978-0-471-70821-6 }}

{{BookCat}}