4Matrices and linear equations
IA Vectors and Matrices
4.2 Inverse of an n × n matrix
For larger matrices, the formula for the inverse is similar, but slightly more
complicated (and costly to evaluate). The key to finding the inverse is the
following:
Lemma.
P
A
ik
∆
jk
= δ
ij
det A.
Proof.
If
i 6
=
j
, then consider an
n × n
matrix
B
, which is identical to
A
except
the
j
th row is replaced by the
i
th row of
A
. So ∆
jk
of
B
= ∆
jk
of
A
, since ∆
jk
does not depend on the elements in row
j
. Since
B
has a duplicate row, we know
that
0 = det B =
n
X
k=1
B
jk
∆
jk
=
n
X
k=1
A
ik
∆
jk
.
If i = j, then the expression is det A by the Laplace expansion formula.
Theorem. If det A 6= 0, then A
−1
exists and is given by
(A
−1
)
ij
=
∆
ji
det A
.
Proof.
(A
−1
)
ik
A
kj
=
∆
ki
det A
A
kj
=
δ
ij
det A
det A
= δ
ij
.
So A
−1
A = I.
The other direction is easy to prove. If
det A
= 0, then it has no inverse,
since for any matrix B, det AB = 0, and hence AB cannot be the identity.
Example.
Consider the shear matrix
S
λ
=
1 λ 0
0 1 0
0 0 1
. We have
det S
λ
= 1.
The cofactors are
∆
11
= 1 ∆
12
= 0 ∆
13
= 0
∆
21
− λ ∆
22
= 1 ∆
23
= 0
∆
31
= 0 ∆
32
= 0 ∆
33
= 1
So S
−1
λ
=
1 −λ 0
0 1 0
0 0 1
.
How many arithmetic operations are involved in calculating the inverse of an
n × n matrix? We just count multiplication operations since they are the most
time-consuming. Suppose that calculating
det A
takes
f
n
multiplications. This
involves
n
(
n −
1)
×
(
n −
1) determinants, and you need
n
more multiplications to
put them together. So f
n
= nf
n−1
+ n. So f
n
= O(n!) (in fact f
n
≈ (1 + e)n!).
To find the inverse, we need to calculate
n
2
cofactors. Each is a
n −
1
determinant, and each takes
O
((
n−
1)!). So the time complexity is
O
(
n
2
(
n−
1)!) =
O(n ·n!).
This is incredibly slow. Hence while it is theoretically possible to solve
systems of linear equations by inverting a matrix, sane people do not do so
in general. Instead, we develop certain better methods to solve the equations.
In fact, the “usual” method people use to solve equations by hand only has
complexity O(n
3
), which is a much better complexity.