Formulas for the determinant, characteristic polynomial and inverses

Calculating determinants, characteristics polynomials and inverses is necessarily expensive, but it doesn't have to be that expensive under specific circumstances.

Important: the normal form for a polynomial when trying to find roots is to divide by the leading coefficient to result in a monic polynomial. Almost ubiquitous is that the characteristic polynomial is described as $\textrm{det}(A - \lambda I_n)$, but in this case, the coefficient of the leading term is $(-1)^n$. By finding $\textrm{det}(\lambda I_n - A)$, the leading term is $\lambda^n$.

1. $2 \times 2$ matrices
2. $3 \times 3$ matrices
3. $4 \times 4$ matrices
4. diagonal, upper-triangular and lower-triangular matrices
5. tri-diagonal matrices
6. elementary matrices
7. isometric (orthogonal and unitary) matrices
8. block-diagonal, block–upper-triangular and block–lower-triangular matrices
9. projectios, perpendicular components and reflections
10. formulas for general matrices

1. General matrices

Given $A, B:\textbf{F}^n \rightarrow \textbf{F}^n$, then

• $\textrm{det}(I_n) = 1$.
• $\textrm{det}(\alpha A) = \alpha^n \textrm{det}(A)$.
• $\textrm{det}(A^*) = \textrm{det}(A)^*$ and $\textrm{det}(A^\top) = \textrm{det}(A)$.
• If $A$ is invertible, $\textrm{det}(A^{-1}) = \frac{1}{\textrm{det}(A)}$.
• $\textrm{det}(A^k) = \textrm{det}(A)^k$ for all $k$ if $A$ is invertible, and for $k \geq 0$ if $A$ is singular.
• $\textrm{det}(BA) = \textrm{det}(B)\textrm{det}(A)$.

If $A$ is block diagonal with blocks $A_{1,1}$ and $A_{2,2}$ being square matrices with dimensions $n_1 + n_2 = n$, respectively, on the diagonal then $\textrm{det}(A) = \textrm{det}(A_{1,1})\textrm{det}(A_{2,2})$. This, of course, generalizes if $A$ is comprised of many blocks on its diagonal.

If $A$ has eigenvalues $\lambda_1, \ldots, \lambda_n$, then $\textrm{det}(A) = \prod_{k = 1}^n \lambda_k$ and $\textrm{tr}(A) = \sum_{k = 1}^n \lambda_k$.

2. $2 \times 2$ matrices

These formulas are easy to memorize.

2.1 Determinant of a $2 \times 2$ matrix

The determinant of the matrix $\left(\begin{array}{cc} a & b \\ c & d \end{array}\right)$ can be calculated as $ad - bc$.

2.1.1 Self-adjoint (symmetric or conjugate symmetric)

The determinant of the self-adjoint matrix $\left(\begin{array}{cc} a & b \\ b^* & d \end{array}\right)$ can be calculated as $ad - |b|^2$ where $a$ and $d$ are real. This is, of course, real even if $b$ is complex, because both eigenvalues are real and the determinant is the product of the eigenvalues.

2.1.2 Skew-adjoint (skew-symmetric or conjugate skew-symmetric)

The determinant of the skew-adjoint matrix $\left(\begin{array}{cc} aj & b \\ -b^* & dj \end{array}\right)$ can be calculated as $-ad + |b|^2$ where $a$ and $d$ are real. This, too, is real even if $b$ is complex, because both eigenvalues are imaginary and the determinant is the product of the eigenvalues.

2.2 Characteristic polynomial of a $2 \times 2$ matrix

The characteristic polynomial of the matrix $\left(\begin{array}{cc} a & b \\ c & d \end{array}\right)$ is $(\lambda - a)(\lambda - d) - bc = \lambda^2 - (a + d)\lambda + ad - bc$ where you will observe that this equals $\lambda^2 - (a + d)\lambda + \textrm{det}(A)$: the determinant is zero if and only if there is a zero eigenvalue.

2.2.1 Self-adjoint (symmetric or conjugate symmetric)

The characteristic polynomial of the self-adjoint matrix $\left(\begin{array}{cc} a & b \\ b^* & d \end{array}\right)$, with $a$ and $d$ real, is $(\lambda - a)(\lambda - d) - |b|^2 = \lambda^2 - (a + d)\lambda + ad - |b|^2$. You will observe that all coefficients are real, but also, the discriminant is $(a + d)^2 - 4(ad - |b|^2) = a^2 + 2ad + d^2 - 4ad + 4|b|^2$ results in $a^2 - 2ad + d^2 + 4|b|^2 = (a - d)^2 + 4|b|^2$, which is non-negative for all possible values of real $a$ and $d$ and complex $b$, meaning that the quadratic must always have real roots because $\frac{a + d}{2}$ also real.

2.2.2 Skew-adjoint (skew-symmetric or conjugate skew-symmetric)

The characteristic polynomial of the skew-adjoint matrix $\left(\begin{array}{cc} aj & b \\ -b^* & dj \end{array}\right)$, with $a$ and $d$ real, is $(\lambda - aj)(\lambda - dj) + |b|^2 = \lambda^2 - (a + d)j \lambda - ad + |b|^2$. You will observe that all coefficients are real, but the discriminant is $(-(a + d)j)^2 - 4(|b|^2 - ad) = -a^2 - 2ad - d^2 + 4ad - 4|b|^2$ results in $-a^2 + 2ad - d^2 - 4|b|^2 = -(a - d)^2 - 4|b|^2$, which is non-positive for all possible values of real $a$ and $d$ and complex $b$, meaning that the quadratic must always have imaginary roots because $\frac{(a + d)j}{2}$ also imaginary.

Of course, the characteristic polynomial of a diagonal, upper-triangular and lower-triangular matrix (as above) is just $(\lambda - a)(\lambda - d)$.

2.3 Inverse of a $2 \times 2$ matrix

The inverse of the matrix $\left(\begin{array}{cc} a & b \\ c & d \end{array}\right)$ is $\frac{1}{ad - bc} \left(\begin{array}{cc} d & -b \\ -c & a \end{array}\right)$, which has a solution if and only if the determinant $ad - bc$ is non-zero.

2.3.1 Self-adjoint (symmetric or conjugate symmetric)

The inverse of the self-adjoint matrix $\left(\begin{array}{cc} a & b \\ b^* & d \end{array}\right)$, with $a$ and $d$ real, is $\frac{1}{ad - |b|^2}\left(\begin{array}{cc} d & -b \\ -b^* & a \end{array}\right)$, which has a solution if and only if the determinatn $ad - |b|^2$ is non-zero.

2.3.2 Skew-adjoint (symmetric or conjugate symmetric)

The inverse of the skew-adjoint matrix $\left(\begin{array}{cc} aj & b \\ -b^* & dj \end{array}\right)$, with $a$ and $d$ real, is $\frac{1}{|b|^2 - ad}\left(\begin{array}{cc} dj & -b \\ b^* & aj \end{array}\right)$, which has a solution if and only if the determinant $|b|^2 - ad$ is non-zero.

3. $3 \times 3$ matrices

3.1 Determinant of a $3 \times 3$ matrix

The determinant of the matrix $\left(\begin{array}{ccc} a & b & c \\ d & e & f \\ g & h & i \end{array}\right)$ can be calculated by writing out the matrix twice:

and then multiplying the three diagonals starting with the first $a$, $b$ and $c$ on the left to get $aei$, $bfg$ and $cdh$ and then multiplying the three anti-diagonals starting with the second $a$, $b$ and $c$ on the right to get $afh$, $bdi$, and $ceg$ and then adding the first and subtracting the second to get $aei + bfg + cdh - afh - bdi - ceg$.

3.1.1 Self-adjoint (symmetric or conjugate symmetric)

The determinant of the self-adjoint matrix $\left(\begin{array}{ccc} a & b & c \\ b^* & e & f \\ c^* & f^* & i \end{array}\right)$ where $a$, $e$ and $i$ are real simplifies to $aei + 2\mathfrak{R}e(bc^*f) - (a|f|^2 + e|c|^2 + i|b|^2)$, which you will note must be real, which must be the case, as the determinant is the product of the eigenvalues, and all eigenvalues of a self-adjoint operator are real.

3.1.2 Skew-adjoint (skew-symmetric or conjugate skew-symmetric)

The determinant of the skew-adjoint matrix $\left(\begin{array}{ccc} aj & b & c \\ -b^* & ej & f \\ -c^* & -f^* & ij \end{array}\right)$ where $a$, $e$ and $i$ are real simplifies to $-aeij - 2\mathfrak{I}m(bc^*f)j + j(a|f|^2 + e|c|^2 + i|b|^2)$, which you will note must be imaginary, which must be the case, as the determinant is the product of the eigenvalues, and all eigenvalues of a skew-adjoint operator are imaginary.

3.2 Characteristic polynomial of a $3 \times 3$ matrix

The characteristic polynomial of the matrix $\left(\begin{array}{ccc} a & b & c \\ d & e & f \\ g & h & i \end{array}\right)$ is $(\lambda - a)(\lambda - e)(\lambda - i) - fh(\lambda - a) - cg(\lambda - e) - bd(\lambda - i) - bfg - cdh$ where you will observe that this equals $\lambda^3 - (a + e + i)\lambda^2 + (ae + ei + ia - bd - cg - fh)\lambda - \textrm{det}(A)$: the determinant is zero if and only if there is a zero eigenvalue.

3.2.1 Self-adjoint (symmetric or conjugate symmetric)

The characteristic polynomial of the self-adjoint matrix $\left(\begin{array}{ccc} a & b & c \\ b^* & e & f \\ c^* & f^* & i \end{array}\right)$ where $a$, $e$ and $i$ are real is $(\lambda - a)(\lambda - e)(\lambda - i) - |f|^2(\lambda - a) - |c|^2(\lambda - e) - |b|^2(\lambda - i) + 2\mathfrak{R}e(bc^*f)$ which expands to $\lambda^3 - (a + e + i)\lambda^2 + (ae + ei + ia - |b|^2 - |c|^2 - |f|^2)\lambda - \textrm{det}(A)$.

3.2.2 Skew-adjoint (skew-symmetric or conjugate skew-symmetric)

The characteristic polynomial of the skew-adjoint matrix $\left(\begin{array}{ccc} aj & b & c \\ -b^* & ej & f \\ -c^* & -f^* & ij \end{array}\right)$ where $a$, $e$ and $i$ are real is $(\lambda - aj)(\lambda - ej)(\lambda - ij) + |f|^2(\lambda - aj) + |c|^2(\lambda - ej) + |b|^2(\lambda - ij) + 2\mathfrak{I}m(bc^*f)$ which expands to $\lambda^3 - (a + e + i)\lambda^2 + (ae + ei + ia - |b|^2 - |c|^2 - |f|^2)\lambda - \textrm{det}(A)$.

4. $4 \times 4$ and higher matrices

These are algorithms that must be implemented or executed by hand.

4.1 Determinant of a $4 \times 4$ matrix and higher

Never use cofactor expansion to find the determinant of a $4 \times 4$ matrix. Instead, while Gaussian elimination uses only row swaps, in calculating the determinant, you can also use column swaps. You can use this to simplify the process of reducing the matrix to an upper-triangular or lower-triangular matrix, in which case, the determinant will be the product of the diagonal entries multiplied by $-1$ raised to the power equal to the number of row and column swaps. Remember to only add multiples of one row onto another or multiples of one column onto another, and do not multiply any row or column by a scalar. There is no situation where cofactor expansion is more efficient.

One may claim that if you use cofactor expansion, it is more efficient in specific circumstances, such as when one can expand upon a row or column containing many zeros, but similarly, we can swap that row or column into the appropriate location when reducing to an upper- or lower-triangular matrix.

For example, to calculate the determinant of the matrix $\left( \begin{array}{rrrrr} 3 & 0 & -1 & 1 & 2 \\ 1 & 0 & 3 & 1 & 1 \\ 3 & 0 & 2 & 0 & -2 \\ -1 & 2 & -2 & 2 & 2 \\ 2 & 0 & 0 & 0 & 1 \end{array}\right)$,
start by swapping Rows 1 and 4 and Columns 1 and 2 to get $\left( \begin{array}{rrrrr} 2 & -1 & -2 & 2 & 2 \\ 0 & 1 & 3 & 1 & 1 \\ 0 & 3 & 2 & 0 & -2 \\ 0 & 3 & -1 & 1 & 2 \\ 0 & 2 & 0 & 0 & 1 \end{array}\right)$,
next, swap Columns 2 and 4 to get $\left( \begin{array}{rrrrr} 2 & 2 & -2 & -1 & 2 \\ 0 & 1 & 3 & 1 & 1 \\ 0 & 0 & 2 & 3 & -2 \\ 0 & 1 & -1 & 3 & 2 \\ 0 & 0 & 0 & 2 & 1 \end{array}\right)$,
and then add $-1$ times Row 2 to Row 4 to get $\left( \begin{array}{rrrrr} 2 & 2 & -2 & -1 & 2 \\ 0 & 1 & 3 & 1 & 1 \\ 0 & 0 & 2 & 3 & -2 \\ 0 & 0 & -4 & 2 & 1 \\ 0 & 0 & 0 & 2 & 1 \end{array}\right)$,
and then add $2$ times Row 3 to Row 4 to get $\left( \begin{array}{rrrrr} 2 & 2 & -2 & -1 & 2 \\ 0 & 1 & 3 & 1 & 1 \\ 0 & 0 & 2 & 3 & -2 \\ 0 & 0 & 0 & 8 & -3 \\ 0 & 0 & 0 & 2 & 1 \end{array}\right)$,
and now the determinant is $(-1)^3 \cdot 2 \cdot 1 \cdot 2 \cdot (8\cdot 1 - 2\cdot(-3)) = -56$, where $3$ is the number of row or column swaps we made and that last term is the determinant of the bottom right $2 \times 2$ matrix (later, we will see that the determinant of a block–upper-triangular matrix is the product of the determinant of the diagonal blocks).

4.2 Characteristic polynomial of a $4 \times 4$ matrix

Because of all of the "nice" $4 \times 4$ orthogonal matrices, it is useful sometimes to use such matrices in performing eigendecompositions; however, finding the characteristic polynomial $\textrm{det}(\lambda I_4 - A)$ is often difficult.

5. Diagonal, upper-triangular or lower-triangular matrices

A matrix $A$ is "diagonal" if $a_{i,j} = 0$ whenever $i \neq j$. A matrix $A$ is "upper-triangular" if $a_{i,j} = 0$ whenever $j < i$, and a matrix $A$ is "lower-triangular" if $a_{i,j} = 0$ whenever $i < j$. The following, respectively, are examles of such matrices when they are square:

$\left(\begin{array}{rrrr} 7 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right)$, $\left(\begin{array}{rrrr} 2 & -1 & 5 & 2 \\ 0 & 7 & 8 & -1 \\ 0 & 0 & 8 & 3 \\ 0 & 0 & 0 & 0 \end{array}\right)$ and $\left(\begin{array}{rrrr} -2 & 0 & 0 & 0 \\ -5 & -3 & 0 & 0 \\ 3 & 7 & 8 & 0 \\ 5 & -2 & 5 & 5 \end{array}\right)$.

A matrix must not necessarily be square to be diagonal, upper-triangular or lower-triangular, but the determiannt, characteristic polynomials and inverses are only defined when the matrix represents a linear operator (that is, it is a square matrix).

5.1 Determinant of a diagonal, upper-triangular or lower-triangular matrix

The determiant of a diagonal, upper-triangular, or lower-triangular $m \times n$ matrix $A$ is the product of the diagonal entries: $\textrm{det}(A) = \prod_{k = 1}^n a_{k,k}$.

5.2 Characteristic polynomial of a diagonal, upper-triangular or lower-triangular matrix

The characteristic polynomial of a diagonal, upper-triangular, or lower-triangular $n \times n$ matrix $A$ is the product $\textrm{det}(\lambda I - A) = \prod_{k = 1}^n (\lambda - a_{k,k})$.

5.3 Inverses of a diagonal, upper-triangular or lower-triangular matrix

A diagonal, upper-triangular or lower-triangular matrix is invertible if and only if all diagonal entries are non-zero.

The inverse of a diagonal matrix $A$ is a diaogonal matrix where each entry on the diagonal is the reciprocal of the corresponding entry in $A$.

The inverse of a upper-triangular matrix is an upper-triangular matrix, and can be calculated iteratively as follows. Given the upper-triangular matrix $A$, let $E$ be its inverse.

1. Set all the entries of $E$ to zero.
2. Assign $e_{i,i} \leftarrow \frac{1}{a_{i,i}}$ for each $i = 1, \ldots, n$.
3. Starting from the the second row from the bottom, so $i = n - 1$, and going up to the top ($i = 1$),
   starting from $j = i + 1$ going up to $n$, calculate the sum of products $\textrm{sp}_{i,j}$ of the $i^\textrm{th}$ row of $A$ and the $j^\textrm{th}$ column of $E$, so $\textrm{sp}_{i,j} = \sum_{k = 1}^n a_{i,k} e_{k,j}$, and set $e_{i,j} \leftarrow -e_{i,i} \textrm{sp}_{i,j}$.

You will note that most of the products are $0$, so so we can simplify $\textrm{sp}_{i,j} = \sum_{k = 1}^n a_{i,k} e_{k,j}$ to $\textrm{sp}_{i,j} = \sum_{k = i+1}^j a_{i,k} e_{k,j}$. This still, however requires $\frac{n^3}{6} + O(n^2)$ multiplications and additions. To give an example:

If $A = \left(\begin{array}{rrrr} 2 & 5 & -7 & 4 \\ 0 & 10 & 3 & -2 \\ 0 & 0 & 5 & 3 \\ 0 & 0 & 0 & -1 \end{array}\right)$, then we start with $E = \left(\begin{array}{rrrr} 0.5 & 0 & 0 & 0 \\ 0 & 0.1 & 0 & 0 \\ 0 & 0 & 0.2 & 0 \\ 0 & 0 & 0 & -1 \end{array}\right)$, and iterate:

First, $-1\cdot 3 = -3$, so $E = \left(\begin{array}{rrrr} 0.5 & 0 & 0 & 0 \\ 0 & 0.1 & 0 & 0 \\ 0 & 0 & 0.2 & 0.6 \\ 0 & 0 & 0 & -1 \end{array}\right)$.

Next, $3\cdot 0.2 = 0.6$ and $3\cdot 0.6 + (-2)(-1) = 3.8$ so we $E = \left(\begin{array}{rrrr} 0.5 & 0 & 0 & 0 \\ 0 & 0.1 & -0.06 & -0.38 \\ 0 & 0 & 0.2 & 0.6 \\ 0 & 0 & 0 & -1 \end{array}\right)$.

Finally, $5\cdot 0.1 = 0.5$, $5 \cdot (-0.06) + (-7)\cdot 0.2 = -1.7$, and $5\cdot(-0.38) + (-7)\cdot 0.6 + 4\cdot(-1) = -10.1$, so $E = \left(\begin{array}{rrrr} 0.5 & -0.25 & 0.85 & 5.05 \\ 0 & 0.1 & -0.06 & -0.38 \\ 0 & 0 & 0.2 & 0.6 \\ 0 & 0 & 0 & -1 \end{array}\right)$.

Here is an implementation:

    // Assume 'A' is an n x n instance of a matrix class
    // that overloads the member operator:
    //     double operator()( unsigned int i, unsigned int j );
    // Assume 'A' is upper triangular
    matrix E{ n }; // Create a n x n zero-matrix

    for ( unsigned int i{ 0 }; i < N; ++i ) {
        E(i, i) = 1.0/A(i, i);
    }

    for ( unsigned int i{ n - 2 }; i < n; --i ) {
    	for ( unsigned int j{ i + 1 }; j < n; ++j ) {
	    double sp{ 0.0 };

            for ( unsigned int k{ i + 1 }; k < j; ++k ) {
                sp += A(i, k)*E(k, j);
            }

            E(i, j) = -E(i,i)*sp;
	}
    }

The inverse of a lower-triangular matrix is an lower-triangular matrix, and can similarly be calculated iteratively as follows. Given the lower-triangular matrix $A$, let $E$ be its inverse.

1. Set all the entries of $E$ to zero.
2. Assign $e_{i,i} \leftarrow \frac{1}{a_{i,i}}$ for each $i = 1, \ldots, n$.
3. Starting from the the second row, so $i = 2$, and going up to the bottom ($i = n$),
   • starting from $j = i - 1$ going down to $1$, calculate the sum of products $\textrm{sp}_{i,j}$ of the $i^\textrm{th}$ row of $A$ and the $j^\textrm{th}$ column of $E$, so $\textrm{sp}_{i,j} = \sum_{k = 1}^n a_{i,k} e_{k,j}$, and set $e_{i,j} \leftarrow -e_{i,i} \textrm{sp}_{i,j}$.

You will note that most of the products are $0$, so so we can simplify $\textrm{sp}_{i,j} = \sum_{k = 1}^n a_{i,k} e_{k,j}$ to $\textrm{sp}_{i,j} = \sum_{k = j}^{i - 1} a_{i,k} e_{k,j}$. This still, however requires $\frac{n^3}{6} + O(n^2)$ multiplications and additions.

Here is an implementation:

    // Assume 'A' is an n x n instance of a matrix class
    // that overloads the member operator:
    //     double operator()( unsigned int i, unsigned int j );
    // Assume 'A' is lower triangular
    matrix E{ n }; // Create a n x n zero-matrix

    for ( unsigned int i{ 0 }; i < N; ++i ) {
        E(i, i) = 1.0/A(i, i);
    }

    for ( unsigned int i{ 1 }; i < n; ++i ) {
    	for ( unsigned int j{ i - 1 }; j < n; --j ) {
	    double sp{ 0.0 };

            for ( unsigned int k{ i + 1 }; k < j; ++k ) {
                sp += A(i, k)*E(k, j);
            }

            E(i, j) = -E(i,i)*sp;
	}
    }

Unlike calculating the inverse of an arbitrary matrix, calculating the inverse of an upper- or lower-triangular matrix is more numerically stable unless the diagonal entries are much smaller in magnitude than the off-diagonal entries.

6. Tri-diagonal matrices

6.1 Determinant of a tri-diagonal matrix

The determinant of a tri-diagonal $n \times n$ matrix $A$ may be found through a recursive formula:

1. Set $d_0 \leftarrow 0$.
2. Set $d_1 \leftarrow a_{1,1}$.
3. For $k$ running from $2$ to $n$,
   set $d_k \leftarrow a_{k,k} d_{k - 1} - a_{k, k-1} a_{k-1, k} d_{k - 2}$.

where $d_n$ is the determinant. Most efficiently, this can be implemented in C++ as

double det( tri_diagonal const &A ) {
    double previous{ 0.0 };
    double current{ A(0, 0) };   // Assume operator()( unsigned int, unsigned int ) is defined

    for ( unsigned int k{ 1 }; k < n; ++k ) {
        double next{ A(k, k)*current - A(k - 1, k)*A(k, k - 1)*previous };
        previous = current;
        current = next;
    }

    return current;
}

6.1.1 Self-adjoint (symmetric or conjugate symmetric)

The determinant of a self-adjoint tri-diagonal $n \times n$ matrix $A$ where $a_{k,k}$ is real may be found through a recursive formula:

1. Set $d_0 \leftarrow 0$.
2. Set $d_1 \leftarrow a_{1,1}$.
3. For $k$ running from $2$ to $n$,
   set $d_k \leftarrow a_{k,k} d_{k - 1} - |a_{k-1, k}|^2 d_{k - 2}$.

where $d_n$ is the determinant. It should be clear that the determinant is real.

6.1.2 Skew-adjoint (skew-symmetric or conjugate skew-symmetric)

The determinant of a skew-adjoint tri-diagonal $n \times n$ matrix $A$ where $a_{k,k}j$ is imaginary may be found through a recursive formula:

1. Set $d_0 \leftarrow 0$.
2. Set $d_1 \leftarrow a_{1,1}j$.
3. For $k$ running from $2$ to $n$,
   set $d_k \leftarrow a_{k,k} d_{k - 1} j + |a_{k-1, k}|^2 d_{k - 2}$.

where $d_n$ is the determinant. It should be clear that the determinant alters between being real or imaginary depending on the parity of the dimension $n$.

6.2 Characteristic polynomial of a tri-diagonal matrix

The characteristic polynomial $\textbf{det}(\lambda I - A)$ of a tri-diagonal $n \times n$ matrix $A$ may be found through a recursive formula:

1. Set $p_0 \leftarrow 0$.
2. Set $p_1 \leftarrow \lambda - a_{1,1}$.
3. For $k$ running from $2$ to $n$,
     set $p_k \leftarrow (\lambda - a_{k,k})p_{k - 1} - a_{k, k-1} a_{k-1, k} p_{k - 2}$.

where $p_n$ is the characteristic polynomial.

6.2.1 Self-adjoint (symmetric or conjugate symmetric)

The characteristic polynomial of a self-adjoint tri-diagonal $n \times n$ matrix $A$ where $a_{k,k}$ is real may be found through a recursive formula:

1. Set $p_0 \leftarrow 0$.
2. Set $p_1 \leftarrow \lambda - a_{1,1}$.
3. For $k$ running from $2$ to $n$,
      set $p_k \leftarrow (\lambda - a_{k,k})p_{k - 1} - |a_{k-1, k}|^2 p_{k - 2}$.

where $p_n$ is the characteristic. It should be clear that the determinant is real.

6.2.2 Skew-adjoint (skew-symmetric or conjugate skew-symmetric)

The characteristic polynomial of a skew-adjoint tri-diagonal $n \times n$ matrix $A$ where $a_{k,k}j$ is imaginary may be found through a recursive formula:

1. Set $p_0 \leftarrow 0$.
2. Set $p_1 \leftarrow \lambda - a_{1,1}j$.
3. For $k$ running from $2$ to $n$,
   set $p_k \leftarrow (\lambda - a_{k,k}j)p_{k - 1} + |a_{k-1, k}|^2 p_{k - 2}$.

where $p_n$ is the characteristic.

6.3 Inverse of a tri-diagonal matrix

Unfortunately, the inverse of a tri-diagonal matrix is almost certainly dense. Consequently, you would not want to calculate the inverse. However, solving a system of linear equations using Gaussian elimination if the matrix is diagonally dominant allows for very fast $O(n)$ algorithms:

    // Assume 'A' is a matrix class that overloads the
    //     double operator()( unsigned int i, unsigned int j );
    // member operator
    // Assume 'x' and 'b' are arrays of capacity N

    // Gaussian elimination
    //   - We assume A is diagonally dominant,
    //     so there will be no reason to swap rows
    for ( unsigned int k{ 1 }; k < N; ++k ) {
	double multiplier{ A(k, k-1)/A(k-1, k-1) };
        A(k, k) = A(k, k) - multiplier*A(k-1, k);
        b[k]    = b[k]    - multiplier*b[k-1];
    }

    // Back substitution
    x[N - 1] = b[N - 1]/A(N-1, N-1);

    for ( unsigned int k{N - 2}; k < N; --k ) {
        x[k] = (b[k] - A(k, k+1)*x[k+1])/A(k,k);
    }

7. Elementary matrices

7.1 Determinant of an elementary matrix

If $R(\theta) = \left(\begin{array}{rr} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{array} \right)$ is the rotation matrix, then:

• The determinant of the matrix that multiples Row $i$ by the non-zero scalar $\alpha$, $E_{\textrm{R}i\verb| *= | \alpha}$ (the identity matrix with entry $(i,i)$ set to $\alpha$), is $\alpha$.
• The determinant of the matrix that swaps Rows $i$ and $j$, $E_{\textrm{R}i \leftrightarrow \textrm{R}j}$ (the identity matrix with Rows $i$ and $j$ swapped), is $-1$.
• The determinant of the matrix that adds $\alpha$ times Row $i$ onto $j$, $E_{\textrm{R}j \verb| += | \alpha \textrm{R}i}$ (the identity matrix with entry $(j,i)$ set to $\alpha$), is $1$.
• The determinant of the matrix that rotates the $i$-$j$ plane by $\theta$, $E_{R(\theta) \textrm{R}i,j}$ (the identity matrix with $e_{i,i} = e_{j,j} = \cos(\theta)$ and $-e_{i,j} = e_{j,i} = \sin(\theta)$), is $1$.

Note: $E_{R(\theta) \textrm{R}i,j}$ rotates the unit vector $\hat{\textbf{e}}_i$ in the direction of $\hat{\textbf{e}}_j$, just like in the $x$-$y$ plane, multiply $R(\theta) \left(\begin{array}{c} 1 \\ 0 \end{array}\right) = \left(\begin{array}{c} \cos(\theta) \\ \sin(\theta) \end{array}\right)$ rotates this vector in the direction of $\left(\begin{array}{c} 0 \\ 1 \end{array}\right)$.

7.2 Characteristic polynomial of an elementary matrix

• The characteristic polynomial of the matrix that multiples Row $i$ by the non-zero scalar $\alpha$, $E_{\textrm{R}i\verb| *= | \alpha}$, is $(\lambda - 1)^{n - 1}(\lambda - \alpha)$.
• The characteristic polynomial of the matrix that swaps Rows $i$ and $j$, $E_{\textrm{R}i \leftrightarrow \textrm{R}j}$, is $(\lambda - 1)^{n - 2}(\lambda^2 - 1)$ with eigenvalues $1$ and $\pm j$.
• The characteristic polynomial of the matrix that adds $\alpha$ times Row $i$ onto $j$, $E_{\textrm{R}j \verb| += | \alpha \textrm{R}i}$, is $(\lambda - 1)^n$.
• The characteristic polynomial of the matrix that rotates the $i$-$j$ plane by $\theta$, $E_{R(\theta) \textrm{R}i,j}$, is $(\lambda - 1)^{n - 2}(\lambda^2 - 2\cos(\theta)\lambda + 1)$ with eigenvalues $1$ and $\cos(\theta) \pm j\sin(\theta)$.

7.3 Inverse of an elementary matrix

• The inverse of the matrix that multiples Row $i$ by the non-zero scalar $\alpha$, $E_{\textrm{R}i\verb| *= | \alpha}$, is $E_{\textrm{R}i\verb| *= | \frac{1}{\alpha}}$.
• The inverse of the matrix that swaps Rows $i$ and $j$, $E_{\textrm{R}i \leftrightarrow \textrm{R}j}$, is itself $E_{\textrm{R}i \leftrightarrow \textrm{R}j}$.
• The inverse of the matrix that adds $\alpha$ times Row $i$ onto $j$, $E_{\textrm{R}j \verb| += | \alpha \textrm{R}i}$, is $E_{\textrm{R}j \verb| += | -\alpha \textrm{R}i}$.
• The inverse of the matrix that rotates the $i$-$j$ plane by $\theta$, $E_{R(\theta) \textrm{R}i,j}$, is $E_{R(-\theta) \textrm{R}i,j}$.

8. Isometric matrices

8.1 Determinant of an isometric matrix

All eigenvalues of an isometric matrix (either orthogonal or unitary) have the property that $|z| = 1$. For an orthogonal matrix $A$, because all complex roots come in complex conjugate pairs, the determinant must be $\textrm{det}(A) = \pm 1$. For a unitary matrix $A$, $|\textrm{det}(A)| = 1$.

8.2 Characteristic polynomial of an isometric matrix

There are no algorithms to more easily find the characteristic polynomial of a isometric matrix than for a general matrix.

8.3 Inverse of an isometric matrix

The inverse of a orthogonal matrix is its transpose. The inverse of a unitary matrix is its conjugate transpose.

9. Block-diagonal, block–upper-triangular and block–lower-triangular matrices

A matrix $A$ is "block diagonal" if there are two square matrices $A_{1,1}$ and $A_{2,2}$ such that $A_{1,1}$ is $n_1 \times n_1$ and $A_{2,2}$ is $n_2 \times n_2$ where $n = n_1 + n_2$ where $A = \left(\begin{array}{cc} A_{1,1} & O_{n_1, n_2} \\ O_{n_2, n_1} & A_{2,2} \end{array}\right)$ where $O_{m,n}$ is an $m \times n$ matrix of zeros.

As matrices $A_{1,1}$ and $A_{2,2}$ may themselves be block diagonal, it may be possible to represent a matrix $A$ as $m$ $n_k \times n_k$ matrices where $n_1 + \cdots + n_m = n$ where $A = \left(\begin{array}{cc} A_{1,1} & O_{n_1, n_2} & \cdots & O_{n_1, n_m} \\ O_{n_2, n_1} & A_{2,2} & \cdots & O_{n_2, n_m} \\ \vdots & \vdots & \ddots & \vdots \\ O_{n_m, n_1} & O_{n_m, n_2} & \cdots & A_{m,m} \end{array}\right)$.

The block $A_{i,j}$ is the $n_i \times n_j$ matrix occupying the entries in the matrix that intersect the rows of $A_{i,i}$ and the columns of $A_{j,j}$.

A matrix $A$ with diagonal blocks $A_{1,1}, \ldots, A_{m,m}$ is "block upper-triangular" if $A_{i,j} = O_{n_i,n_j}$ whenever whenever $j < i$, and a matrix $A$ is "block lower-triangular" if $A_{i,j} = O_{n_i, n_j}$ whenever $i < j$.

9.1 Determinant of a block-diagonal, block–upper-triangular or block–lower-triangular matrix

The determinant of a block-diagonal, block–upper-triangular or block–lower-triangular matrix is equal to the product of the determinants of the blocks: $\textrm{det}(A) = \prod_{k = 1}^m \textrm{det}(A_{k,k}) = \textrm{det}(A_{1,1})\textrm{det}(A_{2,2})\cdots \textrm{det}(A_{m,m})$.

9.2 Characteristic polynomial of a block-diagonal matrix

The characteristic polynomial of a block-diagonal, block–upper-triangular or block–lower-triangular matrix is equal to the product of the characteristic polynomials of the blocks: $\textrm{det}(\lambda I_n - A) = \prod_{k = 1}^m \textrm{det}(\lambda I_{n_k} - A_{k,k}) = \textrm{det}(\lambda I_{n_1} - A_{1,1})\textrm{det}(\lambda I_{n_2} - A_{2,2})\cdots \textrm{det}(\lambda I_{n_m} - A_{m,m})$.

Consequently, the eigenvalues of a block-diagonal matrix is the collection of all the eigenvalues of the individual blocks, and if $\textbf{u}_{k,\ell}$ is an $n_k$-dimensional eigenvector corresponding to the eigenvalue $\lambda_{k,\ell}$ of the $n_k \times n_k$ matrix $A_{k,k}$, then $\textbf{v}_{k,\ell} = \left( \begin{array}{l} \textbf{0}_{n_1} \\ \vdots \\ \textbf{0}_{n_{k - 1}} \\ \textbf{u}_{k,\ell} \\ \textbf{0}_{n_{k + 1}} \\ \vdots \\ \textbf{0}_{n_m} \end{array} \right)$ is an $n$-dimensional eigenvector of $A$ corresponding to $\lambda_{k,\ell}$.

9.3 Inverse of a block-diagonal matrix

A block-diagonal block-diagonal, block–upper-triangular or block–lower-triangular matrix is invertible if and only if all of the diagonal blocks $A_{1,1}, \ldots, A_{m,m}$ are invertible.

The inverse of a block-diagonal matrix $A$ is that matrix with the inverses of the blocks on the diagonal: $A^{-1} = \left(\begin{array}{cc} A_{1,1}^{-1} & O_{n_1, n_2} & \cdots & O_{n_1, n_m} \\ O_{n_2, n_1} & A_{2,2}^{-1} & \cdots & O_{n_2, n_m} \\ \vdots & \vdots & \ddots & \vdots \\ O_{n_m, n_1} & O_{n_m, n_2} & \cdots & A_{m,m}^{-1} \end{array}\right)$.

The inverse of a block–upper-triangular matrix is a block–upper-triangular matrix, and can be calculated as follows: Given the block–upper-triangular matrix, let $E$ be its inverse.

• Set all the entries of $E$ to zero.
• Assign $E_{i,i} \leftarrow A_{i,i}^{-1}$ for each $i = 1, \ldots, m$.
• Starting from the the second row of blocks from the bottom, so $i = m - 1$, and going up to the top ($i = 1$),
  starting from $j = i + 1$ going up to $m$, calculate the product $\textit{SP}_{i,j}$ being the product of the rows of $A$ corresponding to the $i^\textrm{th}$ block multiplied by the columns of $E$ corresponding to the $j^\textrm{th}$ block of $E$, so so $\textit{SP}_{i,j} = \sum_{k = 1}^m A_{i,k} E_{k,j}$, and set $E_{i,j} \leftarrow -E_{i,i} \textit{SP}_{i,j}$.

The inverse of a block–lower-triangular matrix is a block–lower-triangular matrix, and can be calculated as follows: Given the block–lower-triangular matrix, let $E$ be its inverse.

• Set all the entries of $E$ to zero.
• Assign $E_{i,i} \leftarrow A_{i,i}^{-1}$ for each $i = 1, \ldots, m$.
• Starting from the the second row of blocks from the second row of blocks, so $i = 2$, and going down to the bottom ($i = m$),
  starting from $j = i - 1$ going down to $1$, calculate the product $\textit{SP}_{i,j}$ being the product of the rows of $A$ corresponding to the $i^\textrm{th}$ block multiplied by the columns of $E$ corresponding to the $j^\textrm{th}$ block of $E$, so so $\textit{SP}_{i,j} = \sum_{k = 1}^m A_{i,k} E_{k,j}$, and set $E_{i,j} \leftarrow -E_{i,i} \textit{SP}_{i,j}$.

10. Projections and reflections

10.1 The projection

The projection of a vector $\textbf{u}$ onto a vector $\textbf{v}$ is that scalar multiple of $\textbf{v}$ that is closest to $\textbf{u}$ using the 2-norm. The formula is $\textrm{proj}_\textbf{v}(\textbf{u}) = \frac{\langle \textbf{v}, \textbf{u} \rangle}{\langle \textbf{v}, \textbf{v} \rangle} \textbf{v}$. Because the project is linear $\textrm{proj}_\textbf{v}(\alpha_1 \textbf{u}_1 + \alpha_2 \textbf{u}_2) = \alpha_1 \textrm{proj}_\textbf{v}(\textbf{u}_1) + \alpha_2 \textrm{proj}_\textbf{v}(\textbf{u}_2)$, there must be a matrix $P_\textbf{v}$ such that $\textrm{proj}_\textbf{v}(\textbf{u}) = P_\textbf{v} \textbf{u}$.

This matrix is $P_\textbf{v} = \frac{1}{\langle \textbf{v}, \textbf{v}\rangle} |\textbf{v}\rangle\langle\textbf{v}|$, or a scalar times the "outer product". The inner product reduces two vectors to a scalar value, while the outer product converts two vectors into a linear map (matrix). The outer product of two real vectors is the $m \times n$ matrix $|\textbf{u}\rangle\langle\textbf{v}| = (v_1^* \textbf{u} \enspace v_2^* \textbf{u} \; \cdots \; v_n^* \textbf{u})$.

If the dimension of the vector space is greater than $1$, then there is at least one vector $\textbf{u}$ perpendicular to $\textbf{v}$, and thus $P_\textbf{v}\textbf{u} = \textbf{0}_n$, so $0$ is an eigenvalue of $P_\textbf{v}$, and so the determinant is $0$.

The only vectors left unchanged by a projection are multiples of $\textbf{v}$, and the vectors that are mapped to the zero vectore are those perpendicular to $\textbf{v}$. Thus, there is one eigenvalue $1$ and $n - 1$ eigenvalues equal to $0$. Thus, the charcteristic polynomial must be $(\lambda - 1)\lambda^{n - 1}$.

Except in the trivial case when the dimension is $n = 1$, there is no inverse.

The compact eigendecomposition and SVD is where $U = \left( \frac{\textbf{v}}{\|\textbf{v}\|_2} \right)$ with $U(1)U^*$, which you will note is equivalent to our original representation $\frac{\langle \textbf{v}, \textbf{u} \rangle}{\langle \textbf{v}, \textbf{v} \rangle} \textbf{v}$, as the denominator is $\|\textbf{v}\|_2^2$.

The projection operator $P_\textbf{v}$ has properties including being

1. self-adjoint, so $P_\textbf{v}^* = P_\textbf{v}$,
2. idempotent, so $P_\textbf{v}^2 = P_\textbf{v}$,
3. $\textrm{rank}(P_\textbf{v}) = 1$, and
4. $\textrm{det}(P_\textbf{v}) = 0$, and
5. positive semidefinite, so $\langle \textbf{u}, P_\textbf{v} \textbf{u}\rangle \geq 0$, so $P_\textbf{v} \textbf{u}$ never points in the opposite direction of $\textbf{u}$.

10.2 The perpendicular comonent

The perpendicular component of $\textbf{v}$ with respect to $\textbf{v}$ is $\textrm{perp}_\textbf{v}(\textbf{u}) = \textbf{u} - \textrm{proj}_\textbf{v}(\textbf{u})$, and thus may be seen as being equal to $I_n - P_\textbf{v}$. Now, $\textbf{v}$ is mapped to the zero vector, while all vectors orthogonal to $\textbf{v}$ are orthogonal. Thus, the determinant is still zero, and the characteristic polynomial is $(\lambda - 1)^{n - 1}\lambda$. There is, of course, no inverse.

The perpendicular component operator $I_n - P_\textbf{v}$ has properties including being

1. self-adjoint, so $(I_n - P_\textbf{v})^* = I_n - P_\textbf{v}$,
2. idempotent, so $(I_n - P_\textbf{v})^2 = I_n - P_\textbf{v}$,
3. $\textrm{rank}(I_n - P_\textbf{v}) = n - 1$, and
4. $\textrm{det}(I_n - P_\textbf{v}) = 0$, and
5. positive semidefinite, so $\langle \textbf{u}, (I_n - P_\textbf{v}) \textbf{u}\rangle \geq 0$, so $(I_n - P_\textbf{v}) \textbf{u}$ never points in the opposite direction of $\textbf{u}$.

10.3 The reflection

The Householder reflection is a reflection through an $n - 1$-dimensional hyperplane defined by all vectors that are a given vector $\textbf{v}$. The is defined as $\textbf{u} - 2\textrm{proj}_\textbf{v}(\textbf{u})$, and so is also the reflection of $\textbf{u}$ through the perpendicular component $\textrm{perp}_\textbf{v}(\textbf{u})$. Thus, this operator is equal to $I_n - 2P_\textbf{v}$.

The Householder reflection operator $I_n - 2P_\textbf{v}$ has properties including being

1. self-adjoint, so $(I_n - 2P_\textbf{v})^* = I_n - 2P_\textbf{v}$,
2. $\textrm{rank}(I_n - P_\textbf{v}) = n$ and is therefore invertible,
3. self-inverse, so $(I_n - 2P_\textbf{v})^{-1} = I_n - 2P_\textbf{v}$,
4. $\textrm{det}(I_n - 2P_\textbf{v}) = -1$, and
5. isometric, so $\|(I_n - 2P_\textbf{v})\textbf{u}\|_2 = \|\textbf{u}\|_2$ for all vectors $\textbf{u}$.

11. Vandermonde matrices

Given $n$ $x$-values, $x_1$ through $x_n$, the associated Vandermonde matrix is $V = \left(\begin{array}{cccccc} x_1^{n - 1} & x_1^{n - 2} & \cdots & x_1^2 & x_1 & 1 \\ x_2^{n - 1} & x_2^{n - 2} & \cdots & x_2^2 & x_2 & 1 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ x_{n - 2}^{n - 1} & x_{n - 2}^{n - 2} & \cdots & x_{n - 2}^2 & x_{n - 2} & 1 \\ x_{n - 1}^{n - 1} & x_{n - 1}^{n - 2} & \cdots & x_{n - 1}^2 & x_{n - 1} & 1 \\ x_n^{n - 1} & x_n^{n - 2} & \cdots & x_n^2 & x_n & 1 \\ \end{array}\right)$, although, in general, this is a small matrix, such as a $3 \times 3$ or $4 \times 4$: $V = \left(\begin{array}{ccc} x_1^2 & x_1 & 1 \\ x_2^2 & x_2 & 1 \\ x_3^2 & x_3 & 1 \\ \end{array}\right)$ or $V = \left(\begin{array}{cccc} x_1^3 & x_1^2 & x_1 & 1 \\ x_2^3 & x_2^2 & x_2 & 1 \\ x_3^3 & x_3^2 & x_3 & 1 \\ x_4^3 & x_4^2 & x_4 & 1 \\ \end{array}\right)$, respectively.

The determinant of this matrix is $\prod_{i < j}(x_i - x_j)$, and therefore, as this is the product of all possible differences between the $x$-values, this is non-zero so long as all the $x$-values are different.

This matrix does not have an easy inverse, if the $x$ values are equally spaced, the inverse can be calculated; for example, if the $x$ values are $0, -1, -2, \ldots$, then we have $V^{-1} = \left(\begin{array}{rr} 1 & -1 \\ 1 & 0 \\ \end{array}\right)$, $V = \frac{1}{2}\left(\begin{array}{rrr} 1 & -2 & 1 \\ 3 & -4 & 1 \\ 2 & 0 & 0 \\ \end{array}\right)$, $V = \frac{1}{6}\left(\begin{array}{rrrr} 1 & -3 & 2 & -1 \\ 6 & -15 & 12 & -3 \\ 11 & -18 & 9 & -2 \\ 6 & 0 & 0 & 0 \\ \end{array}\right)$ or $V = \frac{1}{24}\left(\begin{array}{rrrrr} 1 & -4 & 6 & -4 & 1 \\ 10 & -36 & 48 & -28 & 6 \\ 35 & -104 & 114 & -56 & 11 \\ 50 & -96 & 72 & -32 & 6 \\ 24 & 0 & 0 & 0 & 0 \\ \end{array}\right)$.

12. Exponential of a matrix

Given a square matrix $A$, then $e^A = I_n + A + \frac{A^2}{2} + \frac{A^3}{6} + \frac{A^4}{24} + \cdots = \sum_{k = 0}^\infty \frac{A^k}{k!}$. $\textrm{det}(e^A) = e^{\textrm{tr}(A)}$, and thus, $e^A$ is always invertible. If $\lambda_1, \ldots, \lambda_n$ are the eigenvalues of $A$, then $e^{\lambda_1}, \ldots, e^{\lambda_n}$ are the eigenvalues of $e^A$.

12. Nilpotent matrix

A matrix is nilpotent if $A^n = 0$ for some $n \geq 0$. nil means "nothing" or "zero" and potens means "powerful" or "having power".

Because $\textrm{det}(A^k) = \textrm{det}(A)^k$, then if $A^n = O$ then $\textrm{det}(A^n) = \textrm{det}(O) = 0$, but $\textrm{det}(A^n) = \textrm{det}(A)^n$, and therefore, combining these two, $\textrm{det}(A) = 0$.