2.2 Matrix algebra

2.2.1 Matrix properties

Determinant: Each n × n square matrix A has an associated scalar number, which is termed as the determinant of that matrix and is noted either by $det(A)$ or by |A|. This value determines whether the matrix has an inverse or not.

When the matrix order is 1, That is, A_1×1 = [a] then we calculate its determinant as |A| = a.

When the matrix order is 2, that is

$\begin{array}{l}\hfill A_{2\times 2}=\left[\begin{array}{ll}\hfill a_1\hfill & \hfill b_1\hfill \\ \hfill a_2\hfill & \hfill b_2\hfill \end{array}\right],\end{array}$

then we have

$\begin{array}{l}\hfill |A|=\left|\begin{array}{ll}\hfill a_1\hfill & \hfill b_1\hfill \\ \hfill a_2\hfill & \hfill b_2\hfill \end{array}\right|=a_1{b}_2-a_2{b}_1.\end{array}$

When the matrix order is 3,

$\begin{array}{l}\hfill A_{3\times 3}=\left[\begin{array}{lll}\hfill a_1\hfill & \hfill b_1\hfill & \hfill c_1\hfill \\ \hfill a_2\hfill & \hfill b_2\hfill & \hfill c_2\hfill \\ \hfill a_3\hfill & \hfill b_3\hfill & \hfill c_3\hfill \end{array}\right],\end{array}$

then we compute the determinant by the following formula:

$\begin{array}{l}\hfill |A|=\left|\begin{array}{lll}\hfill a_1\hfill & \hfill b_1\hfill & \hfill c_1\hfill \\ \hfill a_2\hfill & \hfill b_2\hfill & \hfill c_2\hfill \\ \hfill a_3\hfill & \hfill b_3\hfill & \hfill c_3\hfill \end{array}\right|=a_1\left|\begin{array}{ll}\hfill b_2\hfill & \hfill c_2\hfill \\ \hfill b_3\hfill & \hfill c_3\hfill \end{array}\right|-a_2\left|\begin{array}{ll}\hfill b_1\hfill & \hfill c_1\hfill \\ \hfill b_3\hfill & \hfill c_3\hfill \end{array}\right|+a_3\left|\begin{array}{ll}\hfill b_1\hfill & \hfill c_1\hfill \\ \hfill b_2\hfill & \hfill c_2\hfill \end{array}\right|.\end{array}$

In general, when we have the following general order of matrix A_n×n = [a_ij], then we define the following components:

• The minor of [a_ij] is the determinant of an (n − 1) × (n − 1) submatrix denoted by M_ij. The submatrix M_ij is then obtained from the matrix A_n×n by deleting the row and column containing the element a_ij.

• The signed minor is called cofactor of a_ij denoted by A_ij. The cofactor is a scalar sign being determined by $A_{ij}={(-1)}^{i+j}det(M_{ij}).$ This sign follows the following order:

$\begin{array}{l}\hfill \left[\begin{array}{llllll}\hfill +\hfill & \hfill -\hfill & \hfill +\hfill & \hfill -\hfill & \hfill +\hfill & \hfill \cdots \hfill \\ \hfill -\hfill & \hfill +\hfill & \hfill -\hfill & \hfill +\hfill & \hfill -\hfill & \hfill \cdots \hfill \\ \hfill +\hfill & \hfill -\hfill & \hfill +\hfill & \hfill -\hfill & \hfill +\hfill & \hfill \cdots \hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill \end{array}\right];\end{array}$

• The determinant of matrix A_n×n = [a_ij] is the summed product of the first column entries with its cofactor. That is,

$\begin{array}{l}\hfill |A|=a_{11}{A}_{11}+a_{12}{A}_{12}+\cdots +a_{1n}{A}_{1n}.\end{array}$

Matrix trace: Trace of a square matrix is the summation of matrix diagonal entries $Tr(A)={\sum }_{j=1}^n{a}_{jj}$. Trace of a matrix is also called spur of a square matrix. For square matrices A and B, it is true that

$\begin{array}{ll}\hfill Tr(A)& =Tr(A^T),\hfill \\ \hfill Tr(A+B)& =Tr(A)+Tr(B),\hfill \\ \hfill Tr(\alpha \times A)& =\alpha \times Tr(A),\hfill \end{array}$

where A^T denotes the transpose. The trace is also invariant under a similarity transformation, i.e., if

$\begin{array}{l}\hfill A_1=BA{B}^{-1},\end{array}$

we have

$\begin{array}{l}\hfill Tr(A_1)=Tr(A).\end{array}$

The trace of a product of two square matrices is independent of the order of the multiplication. That is, we have

$\begin{array}{l}\hfill Tr(AB)=Tr(BA).\end{array}$

Therefore, the trace of the commutator of A and B is given by

$\begin{array}{l}\hfill Tr([A,B])=Tr(AB)-Tr(BA)=0.\end{array}$

The trace of a product of three or more square matrices, on the other hand, is invariant only under cyclic permutations of the order of multiplication of the matrices, by a similar argument. The product of a symmetric and an antisymmetric matrix has zero trace, i.e.,

$\begin{array}{l}\hfill Tr(A_S{B}_A)=0.\end{array}$

Matrix rank: The dimension of row space of a matrix is equal to the dimension of the column space of that matrix. The common dimension of the row space and column space of matrix A is defined as the rank of matrix A, denoted by rank(A) = R(A). It is seen that the rank of a matrix is the number of linearly independent vectors and equal to the dimension of space spanned by those vectors. To put it in another way, the rank of A is the number of basis vectors we can form from matrix A, because performing an elementary row operation does not change the row space. To compute the rank of a matrix, we usually perform manipulations on the matrix to bring it into the so-called reduced row echelon form (RREF, also called row canonical form) and subsequently the nonzero rows of the RREF matrix will form the basis for the row space.

A matrix is in RREF if it satisfies the following conditions:

• It is in row echelon form (REF).

• Every leading coefficient is 1 and is the only nonzero entry in its column.

The RREF of a matrix may be computed by Gauss-Jordan elimination. Unlike the REF, the RREF of a matrix is unique and does not depend on the algorithm used to compute it.

The following matrix is an example of one in RREF:

$\begin{array}{l}\hfill \left[\begin{array}{lllll}1& 0& a_1& 0& b_1\\ 0& 1& a_2& 0& b_2\\ 0& 0& 0& 1& b_3\end{array}\right].\end{array}$

Note that this does not always mean that the left of the matrix will be an identity matrix, as this example shows.

For matrices with integer coefficients, the Hermite normal form is an REF that may be calculated using Euclidean division and without introducing any rational number or denominator. On the other hand, the reduced echelon form of a matrix with integer coefficients generally contains noninteger entries.

We assume that A is an m × n matrix, and we define the linear map f by f(x) = Ax. The rank of an m × n matrix is a nonnegative integer and cannot be greater than either m or n, that is,

$\begin{array}{l}\hfill rank(A)\le min(m,n).\end{array}$

A matrix that has rank $min(m,n)$ is said to have full rank; otherwise, the matrix is rank deficient. Note that only a zero matrix has rank zero. f is injective (or “one-to-one”) if and only if A has rank n (in this case, we say that A has full column rank), while f is surjective (or “onto”) if and only if A has rank m (in this case, we say that A has full row rank). If A is a square matrix (i.e., m = n), then A is invertible if and only if A has rank n (i.e., A has full rank). If B is any n × k matrix, then

$\begin{array}{l}\hfill rank(AB)\le min(rank(A),rank(B)).\end{array}$

If B is an n × k matrix of rank n, then

$\begin{array}{l}\hfill rank(AB)=rank(A).\end{array}$

If C is an l × m matrix of rank m, then

$\begin{array}{l}\hfill rank(CA)=rank(A).\end{array}$

The rank of A is equal to r if and only if there exists an invertible m × m matrix X and an invertible n × n matrix Y such that

$\begin{array}{l}\hfill XAY=\left[\begin{array}{ll}\hfill I_r\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill \\ \hfill \hfill \end{array}\right],\end{array}$

where I_r denotes the r × r identity matrix.

Sylvesters rank inequality: if A is an m × n matrix and B is n × k, then

$\begin{array}{l}\hfill rank(A)+rank(B)-n\le rank(AB).\end{array}$

This is a special case of the next inequality. The inequality due to Frobenius: if AB, ABC, and BC are defined, then

$\begin{array}{l}\hfill rank(AB)+rank(BC)\le rank(B)+rank(ABC).\end{array}$

Subadditivity:

$\begin{array}{l}\hfill rank(A+B)\le rank(A)+rank(B),\end{array}$

when A and B are of the same dimension. As a consequence, a rank-k matrix can be written as the sum of k rank-1 matrices, but not fewer. The rank of a matrix plus the nullity of the matrix equals to the number of columns of the matrix. (This is the well-known rank-nullity theorem.) If A is a matrix over the real numbers then the rank of A and the rank of its corresponding Gram matrix are equal. Thus, for real matrices

$\begin{array}{l}\hfill rank(A^{T}A)=rank(A{A}^T)=rank(A)=rank(A^T).\end{array}$

This can be shown by proving equality of their null spaces. The null space of the Gram matrix is given by vectors x for which A^TAx = 0. If this condition is fulfilled, we also have $0=x^T{A}^{T}Ax={\left|Ax\right|}^2.$ If A is a matrix over the complex numbers and A* denotes the conjugate transpose of A, then one has

$\begin{array}{l}\hfill rank(A)=rank(\overline{A})=rank(A^T)=rank(A^{*})=rank(A^{*}A)=rank(A{A}^{*}).\end{array}$

2.2.2 Basic matrix operations

Matrix transpose: Transpose of a matrix is obtained by interchanging all rows with all columns of the matrix. If the matrix size is m × n, the transpose matrix size is n × m.

Matrix addition: If two matrices are of the same order, we then take the summation of any pair of elements, which are at the same position in a peer-to-peer manner in these two matrices to yield the summation. Namely, for two matrices A and B, then the sum of the two matrices C = A + B is a matrix whose entry is equal to the sum of the corresponding entries c_ij = a_ij + b_ij.

Matrix subtraction: When we have two matrices, A and B then the matrix subtraction or matrix difference C = A − B is a matrix whose entry is formed by subtracting the corresponding entry of B from each entry of A, that is c_ij = a_ij − b_ij. Matrix subtraction works only when the two matrices have the same size and the result is also the same size as the original matrices.

Matrix multiplication: One of the most important matrix operations is matrix multiplication or matrix product. The multiplication of two matrices A and B is a matrix C = A × B whose element c_ij consists of the vector inner product of the ith row of matrix A and the jth column of matrix B, that is $c_{ij}={\sum }_{k=1}^m{a}_{ik}{b}_{kj}$. Matrix multiplication can be done only when the number of column of A is equal to the number of rows of B. If the size of matrix A is m × n and the size of matrix B is n × p, then the result of matrix multiplication is a matrix size m by p, or in short A_m×nB_n×p = C_m×p.

Matrix scalar multiple: When we multiply a real number k with a matrix A, we have the scalar multiple of A. The scalar multiple matrix B = kA has the same size of the matrix A and it is obtained by multiplying each element of A by k. That is b_ij = ka_ij.

Hadamard product: Matrix element-wise product is also called Hadamard product or direct product. It is a direct element by element multiplication. If matrix C = AB is the direct product two matrices A and B, then the element of Hadamard product is simply c_ij = a_ij × b_ij. The direct product has the same size as the original matrices.

Horizontal concatenation: It is often useful to think of a matrix composed of two or more submatrices or a block of matrices. A matrix can be partitioned into smaller matrices by setting a horizontal line or a vertical line. For example

$\begin{array}{l}\hfill A=\left(\begin{array}{llll}1& 2& 3& 4\\ 5& 6& 7& 8\\ 9& 0& 1& 2\end{array}\right)=\left[\begin{array}{ll}\hfill A_{11}\hfill & \hfill A_{12}\hfill \\ \hfill A_{21}\hfill & \hfill A_{22}\hfill \end{array}\right].\end{array}$

Matrix horizontal concatenation is an operation to join two sub matrices horizontally into one matrix. This is the reverse operation of partitioning.

Vertical concatenation: Matrix vertical concatenation is an operation to join two sub matrices vertically into one matrix.

Elementary row operation: In linear algebra, there are three elementary row operations. The same operations can also be used for column (simply by changing the word row into column). The elementary row operations can be applied to a rectangular matrix size m × n:

1. interchanging two rows of the matrix;

2. multiplying a row of the matrix by a scalar;

3. add a scalar multiple of a row to another row.

Applying the above three elementary row operations to a matrix will produce a row equivalent matrix. When we view a matrix as the augmented matrix of a linear system, the three elementary row operations are equivalent to interchanging two equations, multiplying an equation by a nonzero constant and adding a scalar multiple of one equation to another equation. Two linear systems are equivalent if they produce the same set of solutions. Since a matrix can be seen as a linear system, applying the above three elementary row operations does not change the solutions of that matrix. The three elementary row operations can be put into three elementary matrices. Elementary matrix is a matrix formed by performing a single elementary row operation on an identity matrix. Multiplying the elementary matrix to a matrix will produce the row equivalent matrix based on the corresponding elementary row operation.

Elementary Matrix Type 1: Interchanging two rows of the matrix

$\begin{array}{l}\hfill r_{12}=E_1=\left[\begin{array}{lll}\hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right],r_{13}=E_1=\left[\begin{array}{lll}\hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right],r_{23}=E_1=\left[\begin{array}{lll}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \end{array}\right].\end{array}$

Elementary Matrix Type 2: Multiplying a row of the matrix by a scalar

$\begin{array}{l}\hfill r_1(k)=E_2=\left[\begin{array}{lll}\hfill k\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right],r_2(k)=E_2=\left[\begin{array}{lll}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill k\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right],r_3(k)=E_2=\left[\begin{array}{lll}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill k\hfill \end{array}\right].\end{array}$

Elementary Matrix Type 3: Add a scalar multiple of a row to another row

$\begin{array}{ll}\hfill & r_{12}(k)=E_3=\left[\begin{array}{lll}\hfill 1\hfill & \hfill k\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right],r_{13}(k)=E_3=\left[\begin{array}{lll}\hfill 1\hfill & \hfill 0\hfill & \hfill k\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right],r_{23}(k)=E_3=\left[\begin{array}{lll}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill k\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right],\hfill \\ \hfill & r_{21}(k)=E_3=\left[\begin{array}{lll}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill k\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right],r_{31}(k)=E_3=\left[\begin{array}{lll}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill k\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right],r_{32}(k)=E_3=\left[\begin{array}{lll}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill k\hfill & \hfill 1\hfill \end{array}\right].\hfill \end{array}$

Reduced row echelon form: There is a standard form of a row equivalent matrix and if we do a sequence of row elementary operations to reach this standard form we may gain the solution of the linear system. The standard form is called RREF of a matrix, or matrix RREF in short. An m × n matrix is called to be in an RREF when it satisfies the following conditions:

1. All zero rows, if any, are at the bottom of the matrix.

2. Reading from left to right, the first non zero entry in each row that does not consist entirely of zeros is a 1, called the leading entry of its row.

3. If two successive rows do not consist entirely of zeros, the second row starts with more zeros than the first (the leading entry of second row is to the right of the leading entry of first row).

4. All other elements of the column in which the leading entry 1 occurs are zeros.

When only the first three conditions are satisfied, the matrix is called in Row Echelon Form (REF). Using Reduced Row Echelon Form of a matrix we can calculate matrix inverse, rank of matrix, and solve simultaneous linear equations.

Finding inverse using RREF (Gauss-Jordan): We can use the three elementary row operations to find the row equivalent of RREF of a matrix. Using the Gauss-Jordan method, you can obtain matrix inverse. Gauss-Jordan method is based on the following theorem: A square matrix is invertible if and only if it is row equivalent to the identity matrix. The method to find inverse using the Gauss-Jordan method is as follows:

• we concatenate the original matrix with the identity matrix;

• perform the row elementary operations to reach RREF;

• if the left part of the matrix RREF is equal to an identity matrix, then the left part is the inverse matrix;

• if the left part of the matrix RREF is not equal to an identity matrix, then we conclude the original matrix is singular. It has no inverse.

Finding a matrix’s rank using RREF: Another application of elementary row operations to find the row equivalent of RREF of the matrix is to find matrix rank. Similar to trace and determinant, the rank of a matrix is a scalar number showing the number of linearly independent vectors in a matrix, or the order of the largest square submatrix of the original matrix whose determinant is nonzero. To compute the rank of a matrix through elementary row operations, simply perform the elementary row operations until the matrix reach the RREF. Then the number of nonzero rows indicates the rank of the matrix.

Singular matrix: A square matrix is singular if the matrix has no inverse. To determine whether a matrix is singular or not, we simply compute the determinant of the matrix. If the determinant is zero, then the matrix is singular.

2.4 Solving system of linear equation

2.4.1 Gauss method

A linear equation in variables x₁, x₂, …, x_n has the form

$\begin{array}{l}\hfill a_1{x}_1+a_2{x}_2+a_3{x}_3+\cdots +a_n{x}_n=d,\end{array}$

where the numbers $a_1,\dots ,a_n\in \mathbb{R}$ are the equation’s coefficients and $d\in \mathbb{R}$ is a constant. An n-tuple $(s_1,s_2,\dots ,s_n)\in {\mathbb{R}}^n$ is a solution of that equation if substituting the numbers s₁, s₂, …, s_n for the variables gives a true statement:

$\begin{array}{l}\hfill a_1{s}_1+a_2{s}_2+a_3{s}_3+\cdots +a_n{s}_n=d.\end{array}$

A system of linear equations

$\begin{array}{ll}\hfill a_{1,1}{x}_1+a_{1,2}{x}_2+& \cdots +a_{1,n}{x}_n=d_1,\hfill \\ \hfill a_{2,1}{x}_1+a_{2,2}{x}_2+& \cdots +a_{2,n}{x}_n=d_2,\hfill \\ \hfill & \cdots \hfill \\ \hfill a_{n,1}{x}_1+a_{n,2}{x}_2+& \cdots +a_{n,n}{x}_n=d_n\hfill \end{array}$

has the solution (s₁, s₂, …, s_n) if that n-tuple is a solution of all of the equations in the system.

Note that each of the above three operations has a restriction. Multiplying a row by 0 is not allowed because obviously that can change the solution set of the system. Similarly, adding a multiple of a row to itself is not allowed because adding −1 times the row to itself has the effect of multiplying the row by 0. Finally, swap ping a row with itself is disallowed.

2.4.2 A general scheme for solving system of linear equation

Linear equation of system can be written into

$\begin{array}{l}\hfill \left[\begin{array}{llll}\hfill a_{11}\hfill & \hfill a_{12}\hfill & \hfill \cdots \hfill & \hfill a_{1n}\hfill \\ \hfill a_{21}\hfill & \hfill a_{22}\hfill & \hfill \cdots \hfill & \hfill a_{2n}\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill a_{m1}\hfill & \hfill a_{m2}\hfill & \hfill \cdots \hfill & \hfill a_{mn}\hfill \end{array}\right]\left[\begin{array}{l}\hfill x_1\hfill \\ \hfill x_2\hfill \\ \hfill ⋮\hfill \\ \hfill x_n\hfill \end{array}\right]=\left[\begin{array}{l}\hfill b_1\hfill \\ \hfill b_2\hfill \\ \hfill ⋮\hfill \\ \hfill b_n\hfill \end{array}\right].\end{array}$

The above linear system can be further simplified into a matrix product Ax = b. A solution of linear system is an order collection of n numbers that satisfies the m linear equations, which can be written in short as a vector solution x. A linear system Ax = b is called a nonhomogeneous system when vector b is not a zero vector. A linear system Ax = 0 is called a homogeneous system when the vector b is a zero vector.

Rank of matrix A denoted by R(A) is used to determine whether the linear system is consistent (has a solution), has many solutions or has a unique set of solutions, or inconsistent (has no solution) using matrix inverse. Diagram of Fig. 2.1 shows the solution of the system of linear equations based on rank of the coefficient matrix R(A) in comparison with the matrix size and rank of the augmented matrix coefficients A and the vector constants b: R(A : b).

The equation Ax = 0 has infinitely many nontrivia solutions if and only if the matrix coefficient A is singular (i.e., it has no inverse, or $det(A)=0$), which happens when the number of equations is less than the unknowns (m < n). Otherwise, the homogeneous system only has the unique trivial solution of x = 0. General solution for homogeneous system is

$\begin{array}{l}\hfill x=(I-A^{-}A)z,\end{array}$

where z is an arbitrary nonzero vector and A⁻ is a generalized inverse ({1}-inverse) matrix of A satisfying AA⁻A = A.

The linear system Ax = b is called consistent if AA⁻b = b. A consistent system can be solved using matrix inverse x = A⁻¹b, left inverse $x=A_L^{-1}b$ or right inverse $x=A_R^{-1}b$. A full rank nonhomogeneous system (happening when $R(A)=min(m,n)$) has three possible options:

• When the number of the unknowns in a linear system is the same as the number of equations (m = n), the system is called uniquely determined system. There is only one possible solution to the system computed using matrix inverse x = A⁻¹b.

• When we have more equations than the unknown (m > n), the system is called overdetermined system. The system is usually inconsistent with no possible solution. It is still possible to find unique solution using left inverse $x=A_L^{-1}b$.

• When you have more unknowns than the equations (m < n), your system is called an undetermined system. The system usually has many possible solutions. The standard solution can be computed using right inverse $x=A_R^{-1}b$.

When a nonhomogeneous system Ax = b is not full rank or when the rank of the matrix coefficients is less than the rank of the augmented coefficients matrix and the vector constants, that is R(A) < R(A : b), then the system is usually inconsistent with no possible solution using matrix inverse. It is still possible to find the approximately least square solution that minimizes the norm of error. That is, using the generalized inverse of the matrix A and by

$\begin{array}{l}\hfill min||b-Ax||,\end{array}$

we obtain

$\begin{array}{l}\hfill x=A^{-}b+(I-A^{-}A)z,\end{array}$

where z is an arbitrary nonzero vector.

2.5 Linear differential equation

2.5.1 Introduction

Linear differential equations are of the form

$\begin{array}{l}\hfill Ly=f,\end{array}$

where the differential operator L is a linear operator, y is the unknown function (such as a function of time y(t)), and the right hand side f is a given function of the same nature as y (called the source term). For a function dependent on time we may write the equation more expressly as

$\begin{array}{l}\hfill Ly(t)=f(t)\end{array}$

and, even more precisely by bracketing

$\begin{array}{l}\hfill L[y(t)]=f(t).\end{array}$

The linear operator L may be considered to be of the form

$\begin{array}{l}\hfill L_n(y)\equiv \frac{d^{n}y}{d{t}^n}+A_1(t)\frac{d^{n-1}y}{d{t}^{n-1}}+\cdots +A_{n-1}(t)\frac{dy}{dt}+A_n(t)y.\end{array}$

The linearity condition on L rules out operations such as taking the square of the derivative of y; but permits, for example, taking the second derivative of y. It is convenient to rewrite this equation in an operator form

$\begin{array}{l}\hfill L_n(y)\equiv [D^n+A_1(t)D^{n-1}+\cdots +A_{n-1}(t)D+A_n(t)]y,\end{array}$

where D is the differential operator d/dt (i.e., Dy = y′, D²y = y″, … ), and A₁(t), …, A_n(t) are given functions. Such an equation is said to have order n; the index of the highest derivative of y that is involved.

If y is assumed to be a function of only one variable, one terms it an ordinary differential equation, else the derivatives and their coefficients must be understood as (contracted) vectors, matrices or tensors of higher rank, and we have a (linear) partial differential equation.

The case where f = 0 is called a homogeneous equation and its solutions are called complementary functions. It is particularly important to the solution of the general case, since any complementary function can be added to a solution of the inhomogeneous equation to give another solution (by a method traditionally called particular integral and complementary function). When the components A_i are numbers, the equation is said to have constant coefficients.

2.5.2 Homogeneous equations with constant coefficients

The first method of solving linear homogeneous ordinary differential equations with constant coefficients is due to Euler, who worked out that the solutions have the form e^zx, for possibly complex values of z. The exponential function is one of the few functions to keep its shape after differentiation, allowing the sum of its multiple derivatives to cancel out the zeros, as required by the equation. Thus, for constant values A₁, …, A_n, to solve

$\begin{array}{l}\hfill y^n+A_1{y}^{(n-1)}+\cdots +A_{n}y=0\end{array}$

by setting y = e^zx leads to

$\begin{array}{l}\hfill z^n{e}^{zx}+A_1{z}^{n-1}{e}^{zx}+\cdots +A_n{e}^{zx}=0.\end{array}$

Division by e^zx gives the nth-order polynomial

$\begin{array}{l}\hfill F(z)=z^n+A_1{z}^{n-1}+\cdots +A_n=0.\end{array}$

This algebraic equation F(z) = 0 is the characteristic equation.

Formally, the terms

$\begin{array}{l}\hfill y^{(k)}(k=1,2,\dots ,n)\end{array}$

of the original differential equation are replaced by z^k. Solving the polynomial then gives n values of z, z₁, …, z_n. Substitution of any of those values for z into e^zx gives a solution $e^{z_{i}x}$. Since homogeneous linear differential equations obey the superposition principle, any linear combination of these functions also satisfy the differential equation.

When the above roots are all distinct, we have n distinct solutions to the differential equation. It can be shown that these are linearly independent, by applying the Vandermonde determinant, and therefore they form a basis of the space of all solutions of the differential equation.

The procedure gives a solution for the case when all zeros are distinct, that is, each has multiplicity 1. For the general case, if z is a (possibly complex) zero (or root) of F(z) having multiplicity m, then for $k\in \{0,1,\dots ,m-1\}$, y = x^ke^zx is a solution of the ordinary differential equation. Applying this to all roots gives a collection of n distinct and linearly independent functions, where n is the degree of F(z). As before, these functions make up a basis of the solution space.

If the coefficients A_i of the differential equation are real, then real-valued solutions are generally preferable. Since nonreal roots z then come in conjugate pairs, so do their corresponding basis functions x^ke^zx, and the desired result is obtained by replacing each pair with their real-valued linear combinations Re(y) and Im(y), where y is one of the pair.

A case that involves complex roots can be solved with the aid of Euler’s formula.

Solving of characteristic equation: A characteristic equation also called auxiliary equation of the form

$\begin{array}{l}\hfill r^2+pr+q=0.\end{array}$

Case 1: Two distinct roots, r₁ and r₂ .

Case 2: One real repeated root, r.

Case 3: Complex roots, α + βi.

In case 1, the solution is given by

$\begin{array}{l}\hfill y=C_1{e}^{r_{1}x}+C_2{e}^{r_{2}x}.\end{array}$

In case 2, the solution is given by

$\begin{array}{l}\hfill y=(C_1+C_{2}x)e^{rx}.\end{array}$

In case 3, using Euler’s equation the solution is given by

$\begin{array}{l}\hfill y=e^{\alpha x}(C_{1}cos\beta x+C_{2}sin\beta x).\end{array}$

2.5.3 Nonhomogeneous equation with constant coefficients

To obtain the solution to the nonhomogeneous equation (sometimes called inhomogeneous equation), find a particular integral yP(x) by either the method of undetermined coefficients or the method of variation of parameters; the general solution to the linear differential equation is the sum of the general solution of the related homogeneous equation and the particular integral. Or, when the initial conditions are set, use Laplace transform to obtain the particular solution directly. Suppose we have

$\begin{array}{l}\hfill \frac{d^{n}y(x)}{d{x}^n}+A_1\frac{d^{n-1}y(x)}{d{x}^{n-1}}+\cdots +A_{n}y(x)=f(x).\end{array}$

For later convenience, define the characteristic polynomial

$\begin{array}{l}\hfill P(v)=v^n+A_1{v}^{n-1}+\cdots +A_n.\end{array}$

We find a solution basis {y₁(x), y₂(x), …, y_n(x)} for the homogeneous (f(x) = 0) case. We now seek a particular integral y_p(x) by the variation of parameters method. Let the coefficients of the linear combination be functions of x, for which we formulate

$\begin{array}{l}\hfill y_p(x)=u_1(x)y_1(x)+u_2(x)y_2(x)+\cdots +u_n(x)y_n(x).\end{array}$

For ease of notation we will drop the dependency on x (i.e., the various (x)). Using the operator notation D = d/dx, the ODE in question is P(D)y = f; so

$\begin{array}{l}\hfill f=P(D)y_p=P(D)(u_1{y}_1)+P(D)(u_2{y}_2)+\cdots +P(D)(u_n{y}_n).\end{array}$

With the constraints

$\begin{array}{ll}\hfill 0=u_1^{\prime }{y}_1+u_2^{\prime }{y}_2+& \cdots +u_n^{\prime }{y}_n\hfill \\ \hfill 0=u_1^{\prime }{y}_1^{\prime }+u_2^{\prime }{y}_2^{\prime }+& \cdots +u_n^{\prime }{y}_n^{\prime }\hfill \\ \hfill & \cdots \hfill \\ \hfill 0=u_1^{\prime }{y}_1^{(n-2)}+u_2^{\prime }{y}_2^{(n-2)}+& \cdots +u_n^{\prime }{y}_n^{(n-2)}\hfill \end{array}$

the parameters commute out,

$\begin{array}{l}\hfill f=u_{1}P(D)y_1+u_{2}P(D)y_2+\cdots +u_{n}P(D)y_n+u_1^{\prime }{y}_1^{(n-1)}+u_2^{\prime }{y}_2^{(n-1)}+\cdots +u_n^{\prime }{y}_n^{(n-1)}.\end{array}$

But P(D)y_j = 0, therefore

$\begin{array}{l}\hfill f=u_1^{\prime }{y}_1^{(n-1)}+u_2^{\prime }{y}_2^{(n-1)}+\cdots +u_n^{\prime }{y}_n^{(n-1)}.\end{array}$

This, with the constraints, gives a linear system in the u_j. Combining the Cramer’s rule with the Wronskian, we have

$\begin{array}{l}\hfill u_j^{\prime }={(-1)}^{n+j}\frac{W{(y_1,\dots ,y_{j-1},y_{j+1}\dots ,y_n)}_{\left(\genfrac{}{}{0ex}{}{0}{f}\right)}}{W(y_1,y_2,\dots ,y_n)}.\end{array}$

In terms of the nonstandard notation used above, one should take the i, n-minor of W and multiply it by f. That’s why we get a minus-sign. Alternatively, forget about the minus sign and just compute the determinant of the matrix obtained by substituting the jth W column with (0, 0, …, f). The rest is a matter of integrating u_j. The particular integral is not unique; y_p + c₁y₁ + ⋯ + c_ny_n also satisfies the ODE for any set of constants c_j.

For interest’s sake, this ODE has a physical interpretation as a driven damped harmonic oscillator; y_p represents the steady state, and c₁y₁ + c₂y₂ is the transient.

2.5.4 Equation with variable coefficients

A linear ODE of order n with variable coefficients has the general form

$\begin{array}{l}\hfill p_n(x)y^{(n)}(x)+p_{n-1}(x)y^{(n-1)}(x)+\cdots +p_0(x)y(x)=r(x).\end{array}$

First-order equation with variable coefficients: A linear ODE of order 1 with variable coefficients has the general form

$\begin{array}{l}\hfill Dy(x)+f(x)y(x)=g(x),\end{array}$

where D is the differential operator. Equations of this form can be solved by multiplying the integrating factor

$\begin{array}{l}\hfill e^{\int f(x)dx}\end{array}$

throughout to obtain

$\begin{array}{l}\hfill Dy(x)e^{\int f(x)dx}+f(x)y(x)e^{\int f(x)dx}=g(x)e^{\int f(x)dx},\end{array}$

which simplifies due to the product rule (applied backwards) to

$\begin{array}{l}\hfill D\left(y(x)e^{\int f(x)dx}\right)=g(x)e^{\int f(x)dx},\end{array}$

which, on integrating both sides and solving for y(x) gives

$\begin{array}{l}\hfill y(x)=e^{-\int f(x)dx}\left(\int g(x)e^{\int f(x)dx}dx+\kappa \right).\end{array}$

In other words, the solution of a first-order linear ODE

$\begin{array}{l}\hfill y^{\prime }(x)+f(x)y(x)=g(x)\end{array}$

with coefficients, that may or may not vary with x, is

$\begin{array}{l}\hfill y=e^{-a(x)}\left(\int g(x)e^{a(x)}dx+\kappa \right),\end{array}$

where κ is the constant of integration, and

$\begin{array}{l}\hfill a(x)=\int f(x)dx.\end{array}$

A compact form of the general solution based on a Green’s function is

$\begin{array}{l}\hfill y(x)={\int }_a^x[y(a)\delta (t-a)+g(t)]e^{-{\int }_t^{x}f(u)du}dt,\end{array}$

where δ(x) is the generalized Dirac delta function.

2.5.5 Systems of linear differential equations

An arbitrary linear ordinary differential equation or even a system of such equations can be converted into a first order system of linear differential equations by adding variables for all but the highest order derivatives. A linear system can be viewed as a single equation with a vector-valued variable. The general treatment is analogous to the treatment above of ordinary first order linear differential equations, but with complications stemming from noncommutativity of matrix multiplication. To solve

$\begin{array}{l}\hfill \left\{\begin{array}{ll}{\mathbf{y}}^{\prime }(x)& =A(x)\mathbf{y}(x)+\mathbf{b}(x),\\ \mathbf{y}(x_0)& ={\mathbf{y}}_0,\end{array}\right.\end{array}$

where y(x) is a vector or matrix, and A(x) is a matrix, let U(x) be the solution of y′(x) = A(x)y(x) with U(x₀) = I (the identity matrix). U is a fundamental matrix for the equation. The columns of U form a complete linearly independent set of solutions for the homogeneous equation. After substituting

$\begin{array}{l}\hfill \mathbf{y}(x)=U(x)\mathbf{z}(x)\end{array}$

the equation

$\begin{array}{l}\hfill {\mathbf{y}}^{\prime }(x)=A(x)\mathbf{y}(x)+\mathbf{b}(x)\end{array}$

is reduced to

$\begin{array}{l}\hfill U(x){\mathbf{z}}^{\prime }(x)=\mathbf{b}(x).\end{array}$

Thus,