Linear Systems of Algebraic Equations

This page presents some topics from Linear Algebra needed for construction of solutions to systems of linear algebraic equations and some applications. We use matrices and vectors as essential elements in obtaining and expressing the solutions.

Symmetric and self-adjoint matrices

Charles Hermite.

As usual, we denote by \( {\bf A}^{\ast} \) the complex conjugate and transposed matrix to the square matrix A, so \( {\bf A}^{\ast} = \overline{{\bf A}^{\mathrm T}} . \) If a matrix A has real entries, then its adjoint \( {\bf A}^{\ast} \) is just transposed \( {\bf A}^{\mathrm T} . \)

A square matrix A is called self-adjoint of Hermitian if \( {\bf A}^{\ast} = {\bf A} . \) Hermitian matrices are named after a French mathematician Charles Hermite (1822--1901), who demonstrated in 1855 that matrices of this form share a property with real symmetric matrices by always having real eigenvalues. Charles was born with a deformity in his right foot which would affect his gait for the rest of his life. He was the first to prove that e, the base of natural logarithms, is a transcendental number. His methods were later used by Ferdinand von Lindemann to prove that π is transcendental. Hermite polynomials, Hermite interpolation, Hermite normal form, Hermitian operators, and cubic Hermite splines are named in his honor. One of his students was Henri Poincaré.

A square matrix Q is called unitary if \( {\bf Q} {\bf Q}^{\ast} = {\bf I} . \) If a matrix Q is unitary, then \( \det {\bf Q} = \pm 1 . \)

We formulate some properities of self-adjoint matrices.

• All eigenvalues of a self-adjoint (Hermitian) matrix are real. Eigenvectors corresponding to different eigenvalues are linearly independent.
• A self-adjoint matrix is not defective; this means that algebraic multiplicity of every eigenvalue is equal to its geometric multiplicity.
• The entries on the main diagonal (top left to bottom right) of any Hermitian matrix are necessarily real, because they have to be equal to their complex conjugate.
• Every self-adjoint matrix is a normal matrix.
• The sum or difference of any two Hermitian matrices is Hermitian. Actually, a linear combination of finite number of self-adjoint matrices is a Hermitian matrix.
• The inverse of an invertible Hermitian matrix is Hermitian as well.
• The product of two self-adjoint matrices A and B is Hermitian if and only if \( {\bf A}{\bf B} = {\bf B}{\bf A} . \) Thus, \( {\bf A}^n \) is Hermitian if A is self-adjoint and n is an integer.
• For an arbitrary complex valued vector v the product \( \left\langle {\bf v}, {\bf A}\, {\bf v} \right\rangle = {\bf v}^{\ast} {\bf A}\, {\bf v} \) is real.
• The sum of a square matrix and its conjugate transpose \( {\bf A} + {\bf A}^{\ast} \) is Hermitian.
• The determinant of a Hermitian matrix is real.

Recall that an \( n \times n \) matrix P is said to be orthogonal if \( {\bf P}^{\mathrm{T}} {\bf P} = {\bf P} {\bf P}^{\mathrm{T}} = {\bf I} , \) the identity matrix; that is, if P has inverse \( {\bf P}^{\mathrm{T}} . \) A nonsingular square complex matrix A is unitary if and only if \( {\bf A}^{\ast} = {\bf A}^{-1} . \)

Example. The matrix

\[ {\bf P} = \begin{pmatrix} 3/5 & 4/5 \\ -4/5 & 3/5 \end{pmatrix} = \frac{1}{5} \, \begin{pmatrix} 3&4 \\ -4&3 \end{pmatrix} \]

is orthogonal. On the other hand, the matrix

\[ {\bf A} = \begin{pmatrix} \frac{1-{\bf j}}{\sqrt{3}} & 0 & \frac{\bf j}{\sqrt{3}} \\ \frac{-1+{\bf j}}{\sqrt{15}} & \frac{3}{\sqrt{15}} & \frac{2{\bf j}}{\sqrt{15}} \\ \frac{1-{\bf j}}{\sqrt{10}} & \frac{2}{\sqrt{10}} & \frac{-2{\bf j}}{\sqrt{10}} \end{pmatrix} \]

is unitary. Here j is a unit vector in positive vertical direction on the complex plane, so \( {\bf j}^2 = -1 . \)

sage: P*u1
sage: P*u2
sage: P*u3

Theorem: A matrix is orthogonal if and only if, as vectors, its columns are pairwise orthogonal.

Theorem: An \( n \times n \) matrix is orthogonal if and only if its columns form an orthnormal basis of \( \mathbb{R}^n . \) ■

A square matrix A is said to be orthogonally diagonalisable if there exists an orthogonal matrix P such that \( {\bf P}^{\mathrm{T}} {\bf A} {\bf P} = {\bf \Lambda} , \) where Λ is a diagonal matrix (of eigenvalues). If P in the above equation is an unitary complex matrix, then we call A unitary diagonalizable.

We can use orthogonal (or unitary) diagonalization to determine a function of a square matrix in exactly the same way as we did in diagonalization section. For instance, we can find the inverse matrix (for nonsingular matrix) \( {\bf A}^{-1} = {\bf P} {\bf \Lambda}^{-1} {\bf P}^{\mathrm T} \) and use it to solve the system of linear algebraic equations A x = b or \( {\bf P} {\bf \Lambda}^{-1} {\bf P}^{\mathrm T}\, {\bf x} = {\bf b} . \) Setting \( {\bf y} = {\bf P}^{\mathrm T} {\bf x} , \) we come across the trivial system of equations \( {\bf \Lambda}^{-1} {\bf y} = {\bf P}^{\mathrm T} {\bf b} ; \) then x = P y. ■

Theorem: An \( n \times n \) matrix A is orthogonally diagonalisable if and only if A is symmetric.

Theorem: An \( n \times n \) matrix A is unitary diagonalisable if and only if A is normal.

Example. We show that the following symmetric (but not self-adjoint) matrix is unitarity diagonalizable:

\[ {\bf A} = \begin{bmatrix} -4+5{\bf j} & 2+ 2{\bf j} & 1-2 {\bf j} \\ 2+ 2{\bf j} & -1+8{\bf j} & -2-2{\bf j} \\ 4+4{\bf j} & -2-2{\bf j} & -4+5{\bf j} \end{bmatrix} , \]

where j is a unit vector in vertical direction on the complex plane \( \mathbb{C} , \) so \( {\bf j}^2 = -1 . \) First, we check that matrix A is normal:

sage: eigenvalues

Then we find its eigenvalues and eigenvectors

sage: eigenvalues

Out of these eigenvectors, we build the matrix S, column by column:

sage: eigenvalues

Finally, we verify that \( {\bf S}^{\ast} {\bf A} {\bf S} = {\bf \Lambda} , \) where Λ is the diagonal mutrix of eigenvalues.

sage: eigenvalues

Orthogonalization of a symmetric matrix: Let A be a symmetric real \( n\times n \) matrix.

Step 1: Find an ordered orthonormal basis B for \( \mathbb{R}^n ;\) you can use the standard basis for \( \mathbb{R}^n .\)

Step 2: Find all the eigenvalues \( \lambda_1 , \lambda_2 , \ldots , \lambda_s \) of A.

Step 3: Find basis for each eigenspace of A (by solving an appropriate homogeneous equation, if necessary).

Step 4: Perform the Gram--Schmidt process on the basis for each eigenspace. Normalize to get an orthonormal basis C.

Step 5: Build the transition matrix S from C, which is an orthogonal matrix and \( {\bf \Lambda} = {\bf S}^{-1} {\bf A} {\bf S} . \)

Example: Consider a symmetric matrix

\[ {\bf A} = \frac{1}{7} \begin{bmatrix} 15&-21&-3&-5 \\ -21&35&-7&0 \\ -3&-7&23&15 \\ -5&0&15& 39 \end{bmatrix} . \]

Its characteristic polynomial \( \chi (\lambda ) = \det \left( \lambda {\bf I} - {\bf A} \right) \) has three distinct roots \( \lambda = 0, 2, 7 \) (double), as Sage confirms:

sage: A = 
sage: A.eigenvalues()
sage: A.fcp()

Solving appropriate homogeneous equations, we determine eigenvectors:

\begin{align*} E_{0} &= \left\{ \left[ 3, 2, 1, 0 \right] \right\} , \\ E_{2} &= \left\{ \left[ 1, 0, -3, 2 \right] \right\} , \\ E_7 &= \left\{ \left[ -2,3,0,1 \right] , \quad \left[ 3,-5,1,0 \right] \right\} . \end{align*}

Since eigenspaces for corresponding simple eigenvalues \( \lambda =0 \quad\mbox{and}\quad \lambda =2 \) are one dimensional, we just divide the corresponding eigenvectors by their norms. This yields orthonormal basis:

\begin{align*} E_{0} &= \left\{ \frac{1}{\sqrt{14}} \left[ 3, 2, 1, 0 \right] \right\} , \\ E_{2} &= \left\{ \frac{1}{\sqrt{14}} \left[ 1, 0, -3, 2 \right] \right\} . \\ \end{align*}

Performing Gram--Schmidt orthogonalizing procedure, we get the eigenspace corresponding to double eigenvalue as a span of two vectors:

\[ E_7 = \left\{ \frac{1}{\sqrt{14}} \left[ -2,3,0,1 \right] , \quad \frac{1}{\sqrt{14}} \left[ 0,-1, 2, 3 \right] \right\} . \]

This allows us to construct the transition matrix and the diagonal matrix of eigenvalues:

\[ {\bf S} = \frac{1}{\sqrt{14}} \begin{bmatrix} 3&1&-2&0 \\ 2&0&3&-1 \\ 1&-3&0&2 \\ 0&2&1&3 \end{bmatrix} , \quad {\bf \Lambda} = \begin{bmatrix} 0&0&0&0 \\ 0&2&0&0 \\ 0&0&7&0 \\ 0&0&0&7 \end{bmatrix} . \]

To find the exponential matrix, we need just to multiply three matrices:

\[ e^{{\bf A} \,t} = {\bf S} e^{{\bf \Lambda} \,t} {\bf S}^{\mathrm T} = \frac{1}{14}\, \begin{bmatrix} 3&1&-2&0 \\ 2&0&3&-1 \\ 1&-3&0&2 \\ 0&2&1&3 \end{bmatrix} \begin{bmatrix} 1&0&0&0 \\ 0&e^{2t} &0&0 \\ 0&0&e^{7t} &0 \\ 070&0& e^{7t} \end{bmatrix} \, \begin{bmatrix} 3&1&-2&0 \\ 2&0&3&-1 \\ 1&-3&0&2 \\ 0&2&1&3 \end{bmatrix} . \]

However, we cannot find the inverse matrix because A is a singular one (λ = 0 is its eigenvalue) and the equation A x = b has a solution not for arbitrary column vector b. To be consistent, the vector b must be orthogonal to the cokernel of A. So we need to solve for y: y^TA = 0 or A^Ty = 0.

Example: The \( n \times n \) matrix with discrete Fourier transform (DFT) entries

\[ {\bf F}_n = n^{-1/2} \left[ \exp \left\{ -2\pi {\bf j} \,\frac{s-1}{n} \right\} \right]_{r,s =1}^n \]

is complex symmetric and unitary matrix (and is a Vandermonde matrix based on the roots of unity). Since \( {\bf F}_n^4 = {\bf I} , \) its minimal polynomial is \( \psi (\lambda ) = \lambda^4 -1 \) for \( n \ge 4 . \) Therefore, this matrix is diagonalizable, and its Lagrange interpolating polynomial, corresponding to an admissible function f, becomes

\[ p(\lambda ) = \frac{1}{4} \left[ f(1) \left( \lambda +1 \right) \left( \lambda^2 +1 \right) - f(-1) \left( \lambda -1 \right) \left( \lambda^2 +1 \right) \right] + \frac{\bf j}{4} \left[ f({\bf j}) \left( \lambda^2 -1 \right)\left( \lambda + {\bf j} \right) - f(-{\bf j}) \left( \lambda^2 -1 \right)\left( \lambda - {\bf j} \right) \right] \]

Now we define a function of a square matrix A by \( f \left( {\bf F}_n \right) = p\left( {\bf F}_n \right) , \) which can be evaluated in \( O(n^2 \log n ) \) operations because multiplication of a vector by \( {\bf F}_n \) can be carried out in \( O(n\, \log n ) \) operations using the fast Fourier transform.