Chapter 3: Inverse Matrices

3.1 Matrices as linear maps . Every matrix A of order m×n can be considered as a mapping from the space Cⁿ (of column vectors of dimension n) to the space C^m in the following way:

If u Î Cⁿ, then Au = v is a vector in C^m which is obtained as a result of the product of the matrix A and the ''matrix'' u. Since A and u have orders m×n and n×1, respectively, the product Au is defined and is a matrix of order m×1, i.e. a column vector in C^m. We denote the mapping defined in this way by the same symbol A, and it always will be clear from the context wheather we are talking about a matrix A or the mapping generated by A.

The mapping A defined above satisfies the following properties which follow immediately from properties (15)-(16)of Chapter 1:

A(lu) = lAu,  A(u+v) = Au+Av,

(1)

for all vectors u, v in Cⁿ and scalars l. Property (1) is equivalent to

A(au+bv) = aAu+bAv

(2)

Because of these properties (1)-(2) the mapping A is called a linear mapping, or a linear transformation, a linear operator, or simply an operator, from the (linear) space Cⁿ to C^m. In the sequel we will just call A an operator.

If Au = v, then v is called the image of u under the mapping A. The set of all image vectors under A is called the range of A, and denoted by R(A).

From the linearlity of A, (1), it follows that R(A) is a linear subset of C^m, i.e. R(A) contains, together with vectors u₁,u₂,...,u_k, all their linear combinations. Linear subsets are called linear subspaces, so that R(A) is a linear subspace of C^m. It may happen that R(A) = C^m (such as for A = I), or R(A) = {0} (such as for A = 0) (where by {0} we denote the subspace consisting of only the zero vector). But in general R(A) is a subspace of C^m which is different from both C^m and {0}. The operator A is said to be onto, or surjective, if its range, R(A), coincides with the whole C^m.

We denote by N(A) the subset of all vectors u Î Cⁿ such that Au = 0. The linearity property of A also implies immediately that N(A) is a linear subset, i.e. a subspace, of Cⁿ. It is called the null-space, or the kernel, of the operator A. It may happen that N(A) = Cⁿ (example: A = 0) or N(A) = {0} (example: A = I), but in general N(A) is a subspace of Cⁿ which is different from both Cⁿ and {0}. It follows immediately from the definitions and the linearity property (1) that A is one-to-one if and only if N(A) = {0}. We will also speak about the range or the kernel of a matrix A as of the corresponding operator associated with A in the above manner.

Let a_k, k = 1,2,..,n denote the k-th column of the matrix A, i.e.

ak =

é ê ê ê ê ê ê ê ë

a1k a2k · · amk

ù ú ú ú ú ú ú ú û

and let e_k, k = 1,2,...,n, be vectors in Cⁿ of the form

ek =

é ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ë

0 0 · · · 1 0 · · 0

ù ú ú ú ú ú ú ú ú ú ú ú ú ú ú ú ú ú û

Then it is easy to see that a_k = Ae_k. Since e_k, k = 1,2,...,n, form a basis of Cⁿ, i.e. the   linear hull  of e_k, k = 1,2,...,n coincides with Cⁿ, it follows that R(A) = L(a₁,...,a_n) and that r(A) is equal to the dimension of R(A).

The correspondence between linear operators from Cⁿ to C^m is one-to-one, in the sense that any linear operator f from Cⁿ to C^m is generated by a matrix A in the above manner. Namely, if we take a matrix A whose colums a_k sastisfies:

a_k = f(e_k,   k = 1,2,...,n,

then A = f.

Theorem 1 If A is a one-to-one operator from Cⁿ to C^m, then n £ m, and rank(A) = n.

Proof: Take any basis of Cⁿ, for instance, the standard basis e₁,...,e_n. Let

v_k = Ae_k,   k = 1,2,...,n.

Since A is one-to-one, it follows that v_k, k = 1,2,..., are linearly independent vectors in C^m. Indeed, if

a₁v₁+a₂v₂+...+a_nv_n = 0,

then

a₁Ae₁+...+a_nAe_n = A(a₁e₁+...+a_ne_n) = 0,

so that

a₁e₁+...+a_ne_n = 0,

(because A is one-to-one), which implies a₁ = a₂ = ... = a_n = 0, since e₁,...,e_n are linearly independent.

Thus, we have found n linearly independent vectors in C^m, which is possible only if m ³ n.

Since Ae_k,   k = 1,2,...,n are linearly independent, we have n £ ran(A). On the other hand, the column rank of A, which is the same as rank(A), is always £ n - the number of columns, we have ran(A) = n.

The following theorem is in a sense '' dual'' to Theorem (1).

Theorem 2 If A is an ''onto'' operator from Cⁿ to C^m, then n ³ m and rank(A) = m.

Proof: Let e₁, e₂,...,e_m be the standard basis of C^m. Since A is ''onto'', there exist u₁,...,u_m in Cⁿ such that Au_k = e_k,k = 1,2,...,m. The vectors u_k, k = 1,2,...,m, are linearly independent. Indeed, if

a₁u₁+...+a_mu_m = 0,

then

A(a₁u₁+...+a_mu_m) = a₁e₁+...+a_me_m = 0,

which implies that a₁ = a₂ = ... = a_m = 0, since e₁,e₂,...,e_m are linearly independent.

Thus, we have found m linearly independent vectors in Cⁿ, so that n ³ m.

Th proof that rank(A) = m is analogous to the proof of the corresponding statement in Theorem 1 and is left as an excercise.

Therems (1) and (2) combined show that an invertible operator exists from Cⁿ to C^m if and only if m = n, i.e. the matrices corresponding to invertible operators are square matrices.

Theorem 3 A square matrix A is invertible if and only if it is silmultaneously one-to-one and onto.

Actually, a stronger statement than theorem 3 holds. Namely, only one of the conditions above above (i.e. ''onto'' or ''one-to-one'') is enough for A to be an invertible matrix. We shall prove this stronger fact later but we also prefer to give a simple direct proof of Theorem 3.

Proof: Assume that A is invertible, i.e. there exists B such that AB = BA = I. If Au = 0, then, multiplying both parts by B from the left, we have, on one hand, BAu = B0 = 0, and on the other hand, BAu = Iu = u. Thus, u = 0. This shows that A is one-to-one.

If v is an arbitrary vector in Cⁿ, we put u = Bv. Then, Au = ABv = Iv = v. Hence, v Î R(A), so that R(A) = Cⁿ, or A is onto.

Conversely, assume that A is one-to-one and onto. Since A is onto, for every v Î Cⁿ there exists an u in Cⁿ such that Au = v. Since A is one-to-one, the element u is unique. Therefore, we can define a mapping B from Cⁿ to Cⁿ by putting

Bv = u.

It is clear that the mapping B is the inverse mapping of A, i.e. ABu = BAu = u for all u Î Cⁿ.

Since if Au₁ = v₁, Au₂ = v₂, then

A(au₁+bu₂) = aAu₁+bAu₂,

it follows that

B(av₁+bv₂) = au₁+bu₂ = aBv₁+bBv₂,

i.e. B is a linear operator. Thus, A is invertibe and A^-1 = B.

Theorem 4 Let A be a square matrix of order n×n, such that ran(A) = n. Then A is invertible.

Proof:According to Theorem 3, one only needs to show that A is one-to-one.

Assume, on the contrary, that A is not one-to-one. Then there exists a nonzero vector x₁ in Cⁿ, such that Ax₁ = 0.

The vector x₁ is linearly independent by itself, and can be complemented by other vectors x₂,..., x_n to a maximal linearly independent subset in Cⁿ. Theorem 5 Let A be a square matrix of order n×n, such that N(A) = {0}. Then A is invertible.

Consider a systems of linear equations

ì ï ï í ï ï î

a11x1+a12x2+...+a1nxn = b1, a21x1+a22x2+...+a2nxn = b2, ¼¼¼ am1x1+am2x2+...+amnxn = bm

(4)

and its matrix form

Ax = b.

(5)

Together with (5) consider also the homogeneous equation

Ax = 0.

(6)

Note that the homogeneous equation (6) always has a solution x = 0. Such a solution is called a trivial solution. A vector x is a solution of the homogeneous equation (5) if and only if x Î N(A). Thus, equation (6) has a nontrivial solution if and only if N(A) ¹ {0}. For general solutions of the nonhomogeneous equation (5) we have the following theorem the proof of which is straightforward.

Theorem 6 Let x₀ be a particular solution of Eq.(5). Then for every x Î N(A), x₀+x is a solution of Eq.(5). Moreover, every solution y of Eq.(5) can be written as y = x₀+x, where x is some solution of the homogenepus equation (6).

It is clear that the system (4)

(i) has at least one solution if and only if b Î R(A);

(ii) has at most one solution if and only if N(A = {0}; and

(iii) has precisely one solution if both (i) and (ii) hold. Thus, we have the following theorem.

Theorem 7 In order for Eq. (4) to have a unique solution for every b Î C^m, it is necessary and sufficient that the operator A is invertible (in particular, m = n).

If the inverse matrix A^-1 is known, then the unique solution og Eq.(4) is obtained by the simple formula

x = A^-1b.

Thus, it is an important question how to find the inverse matrices when they exist. In the next section, we will give a practical method of finding inverse matrices. The formula for the inverse matrices will be given in the next chapter after we introduce the notion of determinant of a matrix.

3.2 Finding the inverse. 3.2.1 Test for the invertibility. Let A be a given square matrix of order n×n. According to Theorem 4, A is invertible if and only if rank(A) = n. In Chapter 2 we have shown that, in order to find rank of A it is enough to reduce A to a row reduced form and count the number of nonzero rows. Since A is a square matrix, its row reduced form is an upper triangular matrix of order n×n whose diagonal elements are 1 or 0. Thus, if some element on the diagonal of the row reduced form of A is zero, then the n-th row of A is a zero row, which implies that rank (A) < n. If none of the elements on the diagonal is zero, then none of the rows are zero row, which implies that rank(A) = n. Thefore, we have the fol

lowing test for the invertibility of a matrix A:

A square matrix A is invertible if and only if its row reduced form has the diagonal consisting of only the unit.

3.2.2 Elementary matrices. Recall that there are three types of elementary row transformations that are used in reduction of a matrix to a row reduced forms: (i) interchanging any two rows, (ii) multiplying a row by a nonzero scalar, and (iii) adding to a row a scalar times another row.

An elementary matrix of order n×n is, by definition, a square matrix of order n×n which is obtained from I_n by applying one of the elementary row transformations listed above.

Thus, there are three types of elementary matrices. The first type consists of matrices which are obtained from I_n by replacing any two rows. We denote elementary matrices of this type by E⁽¹⁾.

The second type consists of matrices which are obtained from I_n by replacing a row by its product with a nonzero scalar. We denote elementary matrices of this type by E⁽²⁾.

The third type consists of matrices which are obtained from I_n by adding to a row a scalar times another row. We denote elementary matrices of this type by E⁽³⁾.

Here are examples of elementary matrices of type 1, 2, and 3, respectively.

E⁽¹⁾ =

é
ê
ê
ê
ê
ê
ë

0	1	0	0
1	0	0	0
0	0	1	0
0	0	0	1

ù
ú
ú
ú
ú
ú
û

  (obtained from   

é
ê
ê
ê
ê
ê
ë

1	0	0	0
0	1	0	0
0	0	1	0
0	0	0	1

ù
ú
ú
ú
ú
ú
û

  by interchanging 1-st and 2-nd rows).

E⁽²⁾ =

é
ê
ê
ê
ê
ê
ë

1	0	0	0
0	1	0	0
0	0	3	0
0	0	0	1

ù
ú
ú
ú
ú
ú
û

   (obtained from   

é
ê
ê
ê
ê
ê
ë

1	0	0	0
0	1	0	0
0	0	1	0
0	0	0	1

ù
ú
ú
ú
ú
ú
û

  by multiplying the third row by 3).

E⁽³⁾ =

é
ê
ê
ê
ê
ê
ë

1	0	0	0
0	1	0	0
0	0	1	0
0	0	3	1

ù
ú
ú
ú
ú
ú
û

  (obtained from   

é
ê
ê
ê
ê
ê
ë

1	0	0	0
0	1	0	0
0	0	1	0
0	0	0	1

ù
ú
ú
ú
ú
ú
û

  by adding to the 4-th row (3)×(the 3-rd row).

One can check directly, that

E⁽¹⁾A is a corresponding elementary row transformation of A,of type (i),

E⁽²⁾A is a corresponding elementary row transformation of A,of type (ii),

E⁽³⁾A is a corresponding elementary row transformation of A,of type (iii).

3.2.3 Constructing the inverse matrix. Assume that A is an invertible matrix. Let us denote the row reduced form of A by A_r = [a_i,j^(r)], and the elementary matrices corresponding to the elementary row transformations that reduce A to A_r by E₁,..., E_k, then we have

Ar = EkEk-1¼E1A.

(7)

As we have seen, the row reduced matrix A_r is a diagonal matrix whose diagonal consists of units. By applying elementary row transformations, it is possible to reduce A_r further to the identity matrix. Indeed, because the a_n,n^(r) = 1, one can apply an elementary row transformation to reduce all elements above a_n,n^(r) to zero. Then, repeating the argument, one can reduce all elements above a_n-1,n-1^(r) to zero, and so on, until we obtain the identity matrix.

Therefore, there are elementary matrices E_k+1,...,E_j such that

I = EjEj-1¼Ek+1Ar.

(8)

From (7) and (8) we have

I = EjEj-1¼E1A,

(9)

which implies that

A^-1 = EjEj-1¼E1

(10)

If we rewrite formula (10) in the obviously equivalent form

A^-1 = E_jE_j-1¼E₁I

then we immediately obtain the following method for practical calculations of inverse matrices:

We write two matrices, side by side: the first one is the given matrix A, and the second one is the identity matrix.

Use the elementary row transformations to reduce A, first to a row reduced form, and then to the identity matrix. Each time, when we applied an elementary row transformation to A, we apply the same transformation to the second matrix. The final matrix at the second place will be the inverse matrix to A.

3.3 LU-Decomposition. The above method of calculating the inverse matrix also suggests a method of a possible factorization of a matrix in to a product of a lower triangular matrix with an upper triangular matrix - a LU-decomposition.

Namely, we consider only elementary matrices of type E⁽³⁾ which correspond to ''adding to a row a scalar times another row''. Moreover, we restrict ourselves to lower triangular matrices of type E⁽³⁾ which correspond to ''adding to a row a scalar times one of the preceding rows''. Below we describe the process of reducing a given matrix A to an upper diagonal form using the above lower triangular elementary matrices.

The first requirement is that a_1,1 ¹ 0. Then there is a lower triangular elementary matrix E₁ such that for the matrix

A₁ = E₁A = [a_i,j⁽¹⁾]

we have a⁽¹⁾_2,1 = 0. Next, we choose a lower triangular elementary matrix E₂ such that for

A₂ = E₂A₁ = [a_i,j⁽²⁾]

we have a⁽²⁾_3,1 = 0, and so on, until we have transformed all elements below a_1,1 to zero.

If the {2,2}-entry of the resulted matrix is zero, then we stop the process, i.e. the LU-decomposition method is not applicable, otherwise we repeat the same process as described above to transform all elements below the {2,2}-entry in to zero. As

suming that we never get a zero element on the diagonal, then there exist lower triangular elementary matrices E₁,...., E_j such that

E_jE_j-1¼E₁A

is an upper triangular matrix, which we denote by A_u. Thus,

EjEj-1¼E1A = Au.

(11)

From (11) it follows that

A = (EjEj-1¼E1)^-1Au = E1^-1E2^-1¼Ej^-1Au.

(12)

Since a product of lower triangular matrices is a lower triangular matrix, and the inverse of a lower triangular matrix is a lower triangular matrix, the matrix

E₁^-1E₂^-1¼E_j^-1

is lower triangular. We denote it by A_l. Thus, (12) implies

A = A_lA_u,

which is a decomposition of A into a product of a lower triangular matrix and an upper triangular matrix. This is called an LU-decomposition of A.

The LU-decomposition is not unique, in general. Indeed, if D is an arbitrary invertible diagonal matrix, then A_lD is lower triangular and D^-1A_u is upper triangular, and

A = (A_lD)(D^-1A_u),

gives another LU-decomposition. However, if we require a normalizing condition that all diagonal elements of A_l be unity, then one can show that the decomposition, if exists, is unique.