Recap: Matrix Inverse

Elementary Row Operations & Elementary Matrix

  • Elementary Row Operations
  • Elementary Matrix
  • Relationships

Elementary Row Operations

There are three types of elementary matrices, which correspond to three types of row operations (respectively, column operations):

  1. Row Switching
  2. Row Multiplication
  3. Row Addition

Elementary Matrix

An square matrix is called an elementary matrix if it can be obtained from an identity matrix of the same size by performing a single elementary row operation.

Relationships

If E is an elementary matrix, to apply the elementary row operation to a matrix A, one multiplies A by the elementary matrix on the left (right for column operations). The elementary matrix for any row operation is obtained by executing the operation on the identity matrix.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import numpy as np

A = np.arange(20).reshape((4,5))

# Row switching
T_RowSwitch = np.identity(4)
T_RowSwitch[1,1] = 0 # Swich the second the forth row
T_RowSwitch[1,3] = 1
T_RowSwitch[3,3] = 0
T_RowSwitch[3,1] = 1
R_RowSwitch = np.matmul(T_RowSwitch, A)

# Row Multiplication
T_RowMul = np.identity(4)
T_RowMul[1,1] = 3 # Multiply the second row entries by 3
R_RowMul = np.matmul(T_RowMul, A)

# Row Addition
T_RowAdd = np.identity(4)
T_RowAdd[2,0] = 1 # Add the first row to the third row
R_RowAdd = np.matmul(T_RowAdd, A)

Inverse

  • Definition
  • How to tell if a matrix is invertible
  • How to find the inverse

Definition

For any square matrix A, if there exist a matrix B of the same size such that
$$ AB = BA = I $$
then A is said to be invertible and B is called an inverse of A.

If no such B can be found, then A is said to be singular.

Note: all elementary matrices are invertible

How to tell if a matrix is invertible

A matrix A is invertible if and only if A can be expressed as the product of elementary matrices.

Or, refering to Elementary Linear Algebra with Applications by Howard Anton
, if A is an n by n matrix, then the following statements are equivalent, that is, all true or all false:

  1. A is invertible
  2. Ax=0 has only the trivial solution
  3. The reduced row echelon form of A is an identity matrix
  4. A is expressible as a product of elementary matrices

In practice, we decides the invertibility of a square matrix by computing its determinant, i.e.,
A square matrix A is invertible if and only if $ det(A) != 0$

How to find the inverse

Over the year, many methods have been develop to find the inverse of a square matrix. Here I only list a few. For more information, see the wikipage

  • Gaussian elimination
  • Eigendecomposition
  • Analytic solution

Gaussian elimination

Finds the inverse of a matrix by decomposing a matix into products of elementary matrices. See here for details.

The computational complexity of the method is $ O(n^3) $. See here for details.

[Eigendecomposition

](https://en.wikipedia.org/wiki/Invertible_matrix#Eigendecomposition)

Analytic solution

Psudo-inverse

See Also

Matrix Decomposition