MATH/APPM 4650
Class notes, April 17
Section 6.3 and 6.4: Inverses and determinants

(6.3) Linear algebra and matrix inversion

Definitions:

• A diagonal matrix is one such that a_ij = 0 whenever i ≠ j. Its off-diagonal components are zero.
• An upper triangular matrix is one with a_ij = 0 whenever i > j. Its below-diagonal components are zero.
• A lower triangular matrix is one with a_ij = 0 whenever i < j. Its above-diagonal components are zero.


• The inverse matrix of A is a matrix B such that AB = BA = I_n, the identity.
• A matrix is singular if it has no inverse, nonsingular if it has an inverse.


• The transpose of a matrix A is a new matrix A^T such that a^T_ij = a_ji. In other words, the matrix is flipped across the diagonal.
• A matrix is symmetric if A^T = A.

One can compute the inverse of a matrix by doing Gauss-Jordan elimination on the augmented matrix

Whatever you get on the right side after reducing the left side to the identity is your inverse.

You can also do Gaussian elimination with backward substitution. This ends up taking about as long though, since instead of just working with one column on the right side, you have a full matrix. We'll discuss this later in the context of factorization.

One reason to do this is if you want to solve the equation Ax = b for the same matrix A but several different vectors b. If B is the inverse of A then the solution is x = Bb. So doing the work once to find B will allow you to quickly get the answer for any b.

If you're only solving the equation once though, it's more efficient not to compute the entire inverse.

Determinants

The determinant of a 2x2 matrix is

| a11	a12 |
| a21	a22 |

= a₁₁a₂₂ - a₁₂a₂₁

The determinant of a 3x3 matrix is

| a11	a12	a13 |
| a21	a22	a23 |
| a31	a32	a33 |

= a₁₁a₂₂a₃₃ + a₁₂a₂₃a₃₁ + a₁₃a₂₁a₃₂ - a₁₂a₂₁a₃₃ - a₁₃a₂₂a₃₁ - a₁₁a₂₃a₃₂

In general, the determinant of an nxn matrix has n! terms (the number of permutations of n elements) and is given by Σ_Sn sgn(σ) a_1σ(1)a_2σ(2)...a_nσ(n) where σ is a permutation of {1,2,...,n} and sgn(σ) is its sign (positive if the number of transpositions is even, negative if it's odd).

Obviously to compute the determinant from the definition takes roughly n! computations. (n or n-1 multiplications for each summand, then n!-1 additions.)

10! = 3,628,800, so computing the determinant is extremely time-consuming.

Thus for example, one would almost never want to compute the determinant before trying to invert a matrix. It's much faster to just try to invert it first and stop if that process fails.

Of course, there are faster ways to compute the determinant.

Expanding on a row (or a column) is not faster.
To compute the determinant of a matrix of size n, you need to do n multiplications and n determinants of size n-1.
Each of those n-1 determinants requires n-1 multiplications and the computation of n-1 determinants of size n-2...
And so on.
We still get an algorithm of size n! or so.

Instead, we can use the Gaussian elimination algorithm (which we know takes O(n³) operations) to reduce the matrix to an upper-triangular matrix.

The determinant does not change when any of the Gaussian elimination operations are used (except switching rows, which multiplies the determinant by -1 each time).

The determinant of an upper triangular matrix is the product of the diagonal terms. So after a reduction, it's only n multiplications to get the determinant.

This is by far the most practical way to compute the determinant of a matrix (unless you have some other information about the matrix).