Generalized Inverses:

How to Invert a Non-Invertible Matrix

S. Sawyer September 7, 2006 rev August 6, 2008
1. Introduction and Definition. Let A be a general mn matrix. Then
a natural question is when we can solve
Ax = y

for x Rm ,

given y Rn

(1.1)

If A is a square matrix (m = n) and A has an inverse, then (1.1) holds if and

only if x = A1 y. This gives a complete answer if A is invertible. However,
A may be m n with m 6= n, or A may be a square matrix that is not
invertible.
If A is not invertible, then equation (1.1) may have no solutions (that
is, y may be not be in the range of A), and if there are solutions, then there
may be many different solutions.

0
2
1 2
, so that
. Then A
=
For example, assume A =
1
0
3 6
A is not invertible. It would be useful to have a characterization of those
y R2 for which it is possible to find a solution of Ax = y, and, if Ax = y is
a solution, to find all possible solutions. It is easy to answer these questions
directly for a 2 2 matrix, but not if A were 8 3 or 10 30.
A solution of these questions can be found in general from the notion of
a generalized inverse of a matrix:
Definition. If A is an m n matrix, then G is a generalized inverse of A
if G is an n m matrix with
AGA = A

(1.2)

If A has an inverse in the usual sense, that is if A is nn and has a two-sided

inverse A1 , then
A1 (AGA)A1 = (A1 A) G (AA1 ) = G
while by (1.2)
A1 (A)A1 = (A1 A)A1 = A1
Thus, if A1 exists in the usual sense, then G = A1 . This justifies the term
generalized inverse. We will see later that any m n matrix A has at least
one generalized inverse G. However, unless A is n n and A is invertible,

Generalized Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
there are many different generalized inverses G, so that G is not unique.
(Generalized inverses are unique is you impose more conditions on G; see
Section 3 below.)
One consequence of (1.2) is that AGAG=AG and GAGA=GA. In general, a square matrix P that satisfies P 2 = P is called a projection matrix .
Thus both AG and GA are projection matrices. Since A is m n and G is
n m, AG is an m m projection matrix and GA is n n.
In general if P is a projection matrix, then P = P 2 implies P y = P (P y)
and P z = z for for all z = P y in the range of P . That is, if P is n n, P
moves any x Rn into V = {P x : x Rn } (the range of P ) and then keeps
it at the same place.
If x Rn , then y = P x and z = x P x = (I P )x satisfies x =
y + z, P y = y, and P z = P (x P x) = P x P 2 x = 0. Since then P x =
P (y + z) = y, we can say that P projects Rn onto its range V along the
space W = {x : P x = 0}.
The two projections AG and GA both appear in the next result, which
shows how generalized inverses can be used to solve matrix equations.
Theorem 1.1. Let A by an mn matrix and assume that G is a generalized
inverse of A (that is, AGA = A). Then, for any fixed y Rm ,
(i) the equation
Ax = y,

x Rn

(1.3)

has a solution x Rn if and only if AGy = y (that is, if and only if y is

in the range of the projection AG).
(ii) If Ax = y has any solutions, then x is a solution of Ax = y if and only
if
x = Gy + (I GA)z

for some z Rn

(1.4)

Remark. If we want a particular solution of Ax = y for y in the range

of A, we can take x = Gy.
Proof of Theorem 1.1. All of the parts of the theorem are easy to prove,
but some involve somewhat unintuitive manipulations of matrices.
Proof of part (i): If y is in the range of the projection AG, that is if
(AG)y = y, then A(Gy) = y and x = Gy is a solution of Ax = y. Conversely,
if Ax = y, then GAx = Gy and AGAx = AGy = (AG)y, while AGA = A
implies AGAx = Ax = y. Thus (AG)y = y. Thus, if Ax = y has any
solutions for a given y Rm , then x = Gy is a particular solution.
Proof of part (ii): This has two parts: First, if AGy = y, then all of
the vectors in (1.4) are solutions of Ax = y. Second, that (1.4) contains all
possible solutions of Ax = y.

Generalized Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
If AGy = y and x = Gy + (I GA)z, then Ax = AGy + A(I GA)z =
y + (A AGA)z = y, so that any x Rn that satisfies (1.4) with AGy = y
is a solution of Ax = y.
Conversely, if Ax = y, let z = x. Then the right-hand side of (1.4) is
Gy + (I GA)x = Gy + x G(Ax) = Gy + x Gy = x, so that any solution x
of Ax = y is given by (1.4) with z = x.

1 2
1 0
Example. Let A =
as before. Set G =
. Then
3 6
0 0

1 2
1 2
1 0
1 2
1 0
1 2
=A
=
=
AGA =
3 6
3 6
3 0
3 6
0 0
3 6
so that G is a generalized inverse of A. The two projections appearing in
Theorem 1.1 are

1 2
1 0
and GA =
AG =
0 0
3 0
In this case

x + 2y
1
x
x
1 2
= (x + 2y)
=
A
=
3
y
3x + 6y
3 6
y

1
Thus Ax = y has a solution x only if y = c
. On the other hand,
3



x
1 0
x
x
1
AG
=
=
=x
y
3 0
y
3x
3

1
so that the range of the projection AG is exactly the set of vectors { c
}.
3

1
The theorem then says that if y = c
, then the set of solutions of Ax = y
3
is exactly


1
z1
x = Gc
+ (I GA)
3
z2

1 0
1
1 0
1 2
z1
=c
+

0 0
3
0 1
0 0
z2

1
0 2
z1
1
2
=c
+
=c
+ z2
(1.5)
0
0 1
z2
0
1

1
It is easy to check that Ax = y = c
for all x in (1.5), and, with some
3
extra work, that these are all solutions.

Generalized Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. The ABCD-Theorem and Generalized Inverses of Arbitrary
Matrices. Let A be an arbitrary m n matrix; that is, with n columns
and m rows. Then we can write

a11 a12 . . . a1n

w1
a21 a22 . . . a2n
w2

.
.
.
.
.
.
.
.
.
.
.
.
A =
= v1 v2 . . . vn = . . .

..
..

..
...
...
.
.
.
wm
am1 am2 . . . amn
where vi are the columns of A and wj are the rows.
In general, the column rank of A (call it rc ) is the dimension of the
vector space in Rm that is spanned by the columns {vi } of A, and the
row rank of A (call it rr ) is the dimension of the vector space in Rn that
is spanned by the rows {wj } of A. That is, rc is the largest number of
linearly-independent columns vi in Rm , and rr is the the largest number of
linearly-independent rows wj in Rn . Then rc m, since the largest number
of linearly independent vectors in Rm is m, and rc n since there are only
n columns to begin with. Thus rc min{m, n}. By the same arguments,
rr min{m, n}.
It can be shown that rc = rr for any m n matrix, so that the row rank
and the column rank of an arbitrary matrix A are the same. The common
value r = rc = rr min{m, n} is called the rank of A.
Let A be an m n matrix with rank(A) = r min{m, n} as above.
Then, one can show that, after a suitable rearrangement of rows and columns,
A can be written in partitioned form as

a b
A =
(2.1)
c d
where a is r r and invertible, b is r (n r), c is (m r) r, and d is
(m r) (n r). In fact, we can prove the following representation theorem
for general matrices:
Theorem 2.1. Let A is an m n matrix with rank r = rank(A). Then the
rows and columns can be permuted so that it can be written in the partitioned
form (2.1) where a is r r and invertible. In that case d = ca1 b, so that

a
b
A =
(2.2)
c ca1 b
(Note that a, b, c, d in (2.1) and (2.2) are matrices, not numbers. Some of
the entries b, c, d in (2.1) may be empty, in which case they do not appear,
for example if m = n and A is invertible.)

Generalized Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

a b
Remarks. If A =
is a 2 2 matrix of numbers with a > 0 but
c d
r = rank(A) = 1, then det(A) = ad bc = 0. This implies d = bc/a. We
cannot write bc/a for matrices, but (2.2) with d = ba1 c is the appropriate
generalization for matrices. The matrix d = ca1 b is always defined and is
(m r) (n r), since c is (m r) r, a1 is r r, and b is r (n r).
Example. Let A = xy 0 be the outer product of vectors x Rm and y Rn ,
so that A is m n. Assume x1 6= 0 and y1 6= 0. Then rank(A) = 1 since
every row of A is a multiple of y and every column of A is a multiple of x.
In this case, we can write

x1 y1

0
x

2
A = xy =
y1 . . .
xm

x1 ( y2

. . . yn )

x2 y2
...
xm y2

...
...
...

x2 yn

...
xm yn

This is in the form (2.2) where b = x1 ( y2 . . . yn ) is a 1 (n 1) row

0
vector, c = y1 ( x2 . . . xm ) is an (m 1) 1 column vector, and

x2
1
x1 ( y2
d = ba1 c = y1 . . .
x1 y1
xm

...

x2
yn ) = . . . ( y2
xm

...

yn )

is the outer product of an (m 1)-dimensional vector and an (n 1)dimensional vector.

Remark. Note that (2.2) can also be written

A =

Ir
ca1

a
(a b) =
a1 ( a
c

a
b) =
( Ir
c

a1 b )

This can be viewed as a generalization of the representation A = uv 0 for an

outer product of two vectors u, v.
Proof of Theorem 2.1. If the first r rows of A are linearly independent
and rank(A) = rank(a) = r in (2.1), then the last m r rows of A are linear
combinations of the first r rows. This means that we can write the last m r
rows of A as
(c d)i =

r
X
j=1

Tij (a b)j

for 1 i m r

Generalized Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
where Tij (1 i m r, 1 j r) are numbers. In terms of matrices,
(c d) = T (a b) = (T a T b)

(2.3)

where T is (m r) r.
The relation (2.3) implies c = T a and hence T = ca1 . This implies
T b = ca1 b = d in (2.3), which completes the proof of Theorem 2.1.
Theorem 2.2. Let

A =

a b
c d

a
b
1
c ca b

(2.4)

be an m n matrix with r = rank(A) where a is r r and invertible, as in

Theorem 2.1. Let
1

a
0
G =
(2.5)
0
0
where the 0s in (2.5) represent matrices of zeroes of dimension sufficient
to make G an n m matrix. Then G is a generalized inverse of A.
Proof. By (2.4) and (2.5)

a b
a
0
a b
c d
0
0
c d

Ir
0
a b
a
b
=
=
ca1 0
c d
c ca1 b

where Ir is the r r unit matrix. This implies AGA = A since d = ca1 b

by (2.4), so that G is a generalized inverse of A.
The two projections in this case are

AG =

Ir
ca1

0
0

and GA =

Theorem 1.1 then says that Ax = y =

y2 Rmr if and only if

AGy =

Ir
ca1

0
0

y1
y2

y1
y2

a1 b
0

Ir
0

can be solved for y1 Rr ,

y1

ca1 y1

y1
y2

Generalized Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
That is, if and only if y2 = ca1 y1 . In that case, the general solution of
Ax = y for x Rn is

x1
= Gy + (Im GA)z
x =
x2
1


a
0
y1
0 a1 b
z1
+
=
0
0
y2
0 Imr
z2

1 1
a y1
a bz2
=
+
0
z2
for arbitrary z2 Rmr .
Remark. This shows that any m n matrix A has at least one generalized
inverse G of the form (2.5). Since often many different linearly-independent
sets of r rows can be permuted to the upper r rows and many different
linearly-independent sets of r columns can be permuted into the first r column positions, a matrix A with rank(A) = r < n can have many different
generalized inverses of this form.
3. The Penrose Inverse. In general, an m n matrix A has many different generalized inverses unless m = n and A is invertible. It is possible,
however, to add conditions to the definition of a generalized inverse so that
there is always a unique generalized inverse under the additional conditions.
Definition. G is called a Penrose inverse of the m n matrix A if G is an
n m matrix that satisfies the four conditions
(i) AGA = A
(ii) GAG = G
(iii) AG = (AG)0 is an orthogonal projection in Rm
(iv) GA = (GA)0 is an orthogonal projection in Rn
Condition (ii) says that A is a generalized inverse of G, in addition to G
being a generalized inverse of A.
The fact than an arbitrary m n matrix A has a unique n m Penrose
inverse follows from the Singular Value Decomposition theorem in matrix
algebra. Some generalized inverses that are natural to use in practice are
Penrose inverses and some are not. The next section gives an example of a
Penrose inverse.
4. Fitted Values in Statistics. Let X be an n r matrix with r < n
and rank(X) = r. Then X 0 X is invertible. If observed values Y Rn can
be exactly fit by the parameters Rr , then
Y = X,

Y Rn , Rr

(4.1)

Generalized Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
The matrix X cannot be invertible, since r < n. However, suppose that
we want a general procedure to choose an arbitrary in terms of Y , in the
hopes that later we can find a justification for this procedure other than it
gives a definite answer. In that case, we can consider a generalized inverse
of X. Specifically, G will be a generalized inverse of X if G is r n and
XGX = X
Since X 0 X is invertible, an obvious choice is
G = (X 0 X)1 X 0

(4.2)

since then XGX = X(X 0 X)1 X 0 X = X. The two projections XG and GX

are
GX = (X 0 X)1 X 0 X = Ir

and

XG = X(X 0 X)1 X 0 = H

(4.3)

Note that both projections are symmetric: That is, Ir = (Ir )0 and H = H 0 .
In addition
GXG = ((X 0 X)1 X 0 )X((X 0 X)1 X 0 ) = (X 0 X)1 X 0 = G
That is, G is the unique Penrose inverse of the n r matrix X.
Theorem 1.1 now says that Y = X can be solved exactly if and only
if (XG)Y = HY = Y ; that is, if and only if Y is in the range of the n n
projection H. Moreover, if HY = Y , then every solution of X = Y is of
the form
= GY = (X 0 X)1 X 0 Y + (Ir GX)z,
= (X 0 X)1 X 0 Y

z Rr
(4.4)

since GX = Ir by (4.3). In other words, if Y = X for some vector , then

the only solution of X = Y for a given Y is given by (4.4).
Indeed, it follows directly from (4.3) that X must be one-one: That is,
if X1 = X2 , then GX1 = GX2 = 1 = 2 .
There is a better motivation for the solution = GY for G in (4.2)
than arbitrariness (or orneriness). Suppose that we view Y as X that are
observed with errors. That is, as
Y = X + e

(4.5)

Generalized Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
where e = {ei } are independent errors. Then we can consider the value of
that minimizes the sum of errors
n
n
X
X

bi 2
Yi (X )
min
Yi (X)i
=

(4.6)

i=1

i=1

If we set
n
n
r
2
X
2
X
X
Yi (X)i
=
Yi
Xia a
j i=1
j i=1
a=1

= 2

n
X
i=1

Yi

r
X

Xia a Xij = 0

a=1

This implies
r X
n
X
a=1 i=1

Xij Xia a =

n
X

Xij Yi ,

1jr

i=1

which can be written in a more compact form as

(X 0 X) = X 0 Y

(4.7)

Since we are assuming that X 0 X is invertible, (4.7) implies

b = (X 0 X)1 X 0 Y = GY
for G in (4.2). That is, the least-squares solution of (4.6) for is given by
= b = GY , where G is the Penrose inverse of the n r matrix X.