In this chapter, some elementary concepts from linear algebra are introduced. The dynamic properties of multi-dimensional state space models are largely determined by a set of commuting matrices. Central to the analysis is the theorem of Schur which states that a set of commuting matrices can simultaneously be triangularized.
We also introduce the singular value decomposition as it is used a lot throughout this thesis. Afterwards the eigenvalues and eigenvectors of commuting matrices are discussed by using the theorem of Schur. We end this brief introductory chapter by introducing the linear matrix pencil, which will be important when describing descriptor systems.
The theorem of Schur
\label{sec:org0e248ed}
A classical result when analyzing commuting matrices is the theorem of Schur. Before introducing this results, we first define a commuting family of matrices.
A family \(F \subseteq M_n\) of matrices is a nonempty finite or infinite set of matrices; a commuting family is a family of matrices in which every pair of matrices commutes. The set \(M_n\) is the set of all square real matrices of size \(m\times m\).
The theorem of Schur~\cite{horn2012matrix} states that a commuting family of matrices can be simultaneously placed in an upper triangular form, where every matrix is a block diagonal matrix. Every block in this form, has a single eigenvalue on the main diagonal. This result is formulated in the next theorem.
Let \(\mathcal{F} \subset M_n\) be a commuting family. There is a non-singular \(S \in M_n\) and positive integers \(k,n_1,\dots, n_k\) such that \(n_1+ \dots + n_k = n\) and, for every \(A \in \mathcal{F}, S^{-1}AS = A_1 \oplus \dots \oplus A_k\) is block diagonal with \(A_i \in M_{n_i}\) for each \(i= 1,\dots,k\). Moreover, each diagonal block \(A_i\) is upper triangular and has exactly one eigenvalue.
Using this theorem simplifies the analysis of commuting matrices because we can always assume that there exists a basis transformation which places all matrices in a block diagonal form. A lot of results can first be proven for commuting matrices with a single eigenvalue, and than extended to the general case by using Theorem~\ref{thm:commuting_all_block_diagonal}.
The singular value decomposition
A matrix decomposition, also know as a matrix factorization is the mathematical operation of writing a given matrix as the product of a different set of matrices. Every factorization has its own applications and properties. Examples of matrix factorizations include;
- the QR-decomposition,
- the eigenvalue and Jordan decomposition,
- Schur decomposition,
- Singular value decomposition.
In this thesis, the singular value decomposition (\gls{SVD}) plays an important role in all presented algorithms and much of the system theory.
Every matrix is characterized by four fundamental spaces, the column space, the row space, the left null space and the right null space. The column space of a matrix is the vector space span by the columns of a matrix, whereas the row space of a matrix is the space span by its rows. The left null space of a matrix is the vector space of all vectors which are orthogonal to the column space, and the right null space are all vectors which are orthogonal to the row space. The singular value decomposition allows us to calculate an orthonormal basis for all four spaces.
Given a rectangular matrix \(A\). The singular value decomposition of this matrix is given by
\begin{equation} A = U \Sigma V^T = \begin{bmatrix} U_0 & U_1 \end{bmatrix} \begin{bmatrix} \Sigma_0 & 0 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} V_0^T \\ V_1^T \end{bmatrix}. \end{equation}
The matrix \(\Sigma_0\) is a diagonal matrix with strictly positive real elements on the diagonal, which are called the singular values of \(A\). The rank of the matrix is equal to the number of non-zero singular values. Both matrices \(U\) and \(V\) contain respectively the left and right singular vector and are orthonormal matrices, meaning that
\begin{equation} U U^T = \eye~\text{and}~V^T V = \eye. \end{equation}
Where \(\eye\) is the identity matrix. This implies that the columns of \(U\) and the rows of \(V\) form a orthonormal basis. The columns of \(U_0\) form an orthonormal basis of the column space of \(A\) and the the rows of \(V_0\) form an orthonormal basis for the row space of \(A\).
Generalized eigenbasis for commuting matrices
Related to theorem of Schur, we introduce the generalized eigenbasis for a family of commuting matrices.
Theorem and definitions
\label{sec:org73d4c2c} We first define the generalized eigenbasis for a pair of commuting matrices.
For two real commuting matrices \(A\) and \(B\) \(\in \real^{m\times m}\), we define
\begin{equation*} X = \left\lbrace x_1, x_2, \dots, x_m\right\rbrace \end{equation*}
as a basis of \(\complex^m\). The vectors \(x_i\) are called the generalized eigenvectors of the commuting matrix pair \((A,B)\). All basis vectors \(x_i\) satisfy
\begin{equation} \label{eqn:geneigenbasis1} \begin{matrix} (\eye\lambda_i-A)^{n_i} x_i = 0 \\ (\eye\gamma_i-B)^{m_i} x_i = 0, \\ \end{matrix} \end{equation}
and
\begin{equation} \label{eqn:geneigenbasis2} \begin{matrix} (\eye\lambda_i-A)^{n_i-1} x_i \neq 0 \\ (\eye\gamma_i-B)^{m_i-1} x_i \neq 0 \\ \end{matrix} \end{equation}
for some values \(\lambda_i\) and \(\gamma_i\) and some integers \(n_i\) and \(m_i\). With every generalized eigenvector \(x_{i}\), a pair of eigenvalues \((\lambda_i,\gamma_i)\) and a pair of orders \((n_{i},m_{i})\) is associated. The values \(\lambda_i\) and \(\gamma_i\) also correspond to the eigenvalues of respectively \(A\) and \(B\).
For every pair of real commuting matrices \(A\) and \(B\) \(\in \real^{m\times m}\), the generalized eigenbasis exists. Furthermore, With every vector \(x_i\) two Jordan chains are associated
\begin{equation} C_A(x_i) = \left\{ x_i, (A-\lambda_i)x_i,\cdots, (A-\lambda_i)^{n_i-1}x_i \right\} \end{equation}
and
\begin{equation} C_B(x_i) = \left\{ x_i, (B-\gamma_i)x_i,\cdots, (B-\gamma_i)^{m_i-1}x_i \right\} \end{equation}
Example
\label{sec:org6e6f28f} \label{sec:intro-example-commuting}
Theorem \ref{thm:commuting} generalizes the concept of an eigenbasis to the set of two commuting matrices. One could wrongly conclude that Theorem \ref{thm:commuting} states that two commuting matrices can simultaneously be put in a Jordan canonical form. This however is not true, which can be demonstrated with a small counter example. Take two commuting matrices \(A\) and \(B\)
\begin{equation} A = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ \end{bmatrix}, B = \begin{bmatrix} 2 & 0 & 1 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \\ \end{bmatrix}. \end{equation}
Both matrices have a single eigenvalue, 1 and 2 respectively for \(A\) and \(B\). Via a direct calculation it is clear that both matrices commute, such that \(AB=BA\). Define \(X = \lbrace x_1,x_2,x_3\rbrace\) to be the set of generalized eigenvectors, given by
\begin{equation}\label{eqn:standardnormal} x_1 = \begin{bmatrix}1 \\ 0 \\ 0\end{bmatrix}, x_2 = \begin{bmatrix}0 \\ 1 \\ 0\end{bmatrix}, x_3 = \begin{bmatrix}0 \\ 0 \\ 1\end{bmatrix}. \end{equation}
The vectors in \(x_1, x_2\) and \(x_3\) form a spacial basis of \(\real^3\), often referred to as the standard normal basis. Now it is easy to check that
\begin{equation} \begin{aligned} (\eye-A)x_1 = (\eye-A)^2x_2 = (\eye-A)^{3}x_3 = 0, \\ (2\eye-B)x_1 = (2\eye-B)x_2 = (2\eye-B)^2x_3 = 0. \end{aligned} \end{equation}
The order and eigenvalue pair for the three vectors \(x_i\) are summarized in Table~\ref{tbl:order_example}.
In this basis, only the matrix \(A\) is put in the Jordan canonical form, while the matrix \(B\) is not. This basis however, puts both matrices simultaneously in the Weyr canonical form \cite{weyr1885repartition,o2011advanced}, which is a different lesser known Canonical form.
\begin{table} \centering \caption[Order and eigenvalues of a set of commuting matrices.] {Order and value to the eigenvalues of the commuting matrix pair form the example in Section \ref{sec:intro-example-commuting}.} \label{tbl:order_example} \begin{tabular}{ |c|c|c| } \hline Vector & Eigenvalue & Order \\ \hline \hline $x_1$ & (1,2) & (1,1) \\ $x_2$ & (1,2) & (2,1) \\ $x_2$ & (1,2) & (3,2) \\ \hline \end{tabular} \end{table}
Proof
% We proof Theorem~\ref{thm:commuting} by using the the Theorem of Schur.
Consider two commuting matrices \(A\) and \(B\) of size \(m \times m\). According to the theorem of Schur, there exists a unitary matrix \(U\) such that
\begin{equation} U^{-1}AU = \begin{bmatrix} A_0 & & & \\ & A_1& & \\ & & \ddots & \\ & & & A_n \\ \end{bmatrix}, U^{-1}BU = \begin{bmatrix} B_0 & & & \\ & B_1& & \\ & & \ddots & \\ & & & B_n \\ \end{bmatrix}. \end{equation}
Each block \(A_i\) and \(B_i\) is an upper triangular matrix with a constant diagonal and has a size \(m_i\times m_i\). Denote the element on the diagonal respectively with \(\lambda_i\) and \(\gamma_i\). We introduce two new matrices
\begin{equation} D = \lambda_i\eye - A_i, E = \gamma_i \eye - B_i. \end{equation}
Both matrices are nilpotent as they are upper triangular matrices with zeros on the diagonal. Take a basis \(X_i = \lbrace x_{i,1} \dots x_{i,n_i}\rbrace\) of \(\complex^{m_i}\). For every vector \(x_{i,j}\) from this basis there exists two integers \(\mu_{i,j}\) and \(\nu_{i,j}\) such that
\begin{equation} \begin{matrix} (\eye\lambda_i-A_i)^{\mu_{i,j}} x_{i,j} = 0 \\ (\eye\gamma_i-B_i)^{\mu_{i,j}} x_{i,j} = 0, \end{matrix} \end{equation}
and
\begin{equation} \begin{matrix} (\eye\lambda_i-A_i)^{\mu_{i,j}-1} x_{i,j} \neq 0 \\ (\eye\gamma_i-B_i)^{\mu_{i,j}-1} x_{i,j} \neq 0, \end{matrix} \end{equation}
This follows directly from the nilpotency of \(D\) and \(E\) and proves that the basis \(X_i\) is a generalized eigenbasis of \(A_i\) and \(B_i\). The basis formed as the direct sum
\begin{equation} X = X_1 \oplus X_2 \cdots \oplus X_n \end{equation}
satisfies the condition of Theorem~\ref{def:ch1-gen-eigenbasis}.
Extension to multiple matrices
\label{sec:org5b4c5bc} The results formulated in Theorem \ref{thm:commuting} can be extended a commuting family.
Let \(\mathcal{F} \subset M_n\) be a commuting family. We define
\begin{equation} X = \left\lbrace x_1, x_2, \dots, x_m\right\rbrace \end{equation}
as a basis of \(\complex^m\). The vectors \(x_i\) are called the generalized eigenvectors of the commuting family \(\mathcal{F}\). For every element \(A\in \mathcal{F}\), all basis vectors \(x_i\) satisfy
\begin{equation} \label{eqn:geneigenbasis1-mult} \begin{matrix} (\eye\lambda_i-A)^{n_i} x_i = 0 \\ \end{matrix} \end{equation}
and
\begin{equation} \label{eqn:geneigenbasis2-mult} \begin{matrix} (\eye\lambda_i-A)^{n_i-1} x_i \neq 0 \\ \end{matrix} \end{equation}
for some value of \(n_i\) and \(\lambda_i\).
Every commuting family has a general eigenbasis.
The proof of this theorem follows the same steps as the previous proof for two matrices and is left out of this thesis.
Linear matrix pencils
In this thesis, we will introduce descriptor systems and their multi-dimensional generalization. Descriptor systems are parameterized by two square matrices, which form a linear matrix pencil. In general, a matrix pencil of degree \(l>0\), is defined as \(L(\lambda)=\sum _{{i=0}}^{l}\lambda^{i}A_{i}\), with \(A_i\) a complex \(m \times m\) matrix and \(A_{l}\neq 0\). A linear matrix pencil is a matrix pencil of degree 1 and is denoted as \((A,E) = A - \lambda E\). The roots of a matrix pencil are all complex values \(\lambda_0\) such that the matrix \(L(\lambda_0)\) becomes rank deficient. The eigenvalues of a matrix \(A\) are the roots of the matrix pencil \((A,\eye)\).
Regular, Standard and commuting matrix pencils
Three important categories of matrix pencils are regular, standard and commuting matrix pencils. In this section these three types of matrix pencils are briefly introduced and discussed.
Regular pencils
A matrix pencil \((A,E)\) for which
\begin{equation} \det(Es-A) = p(s) \end{equation}
is not identically zero is called a regular pencil~\cite{Ikramov1993,golub13}. For every regular pencil, there exists a \(\mu\) such \(p(\mu)\neq 0\). Non-regular matrix pencils are not consider in this thesis.
Suppose that the matrix pencil \((A,E)\) is not regular such that \(\det(sE-A) = 0\). This means that the matrix \(sE-A\) is rank deficient for all values of \(s\) and there exist a vector \(x\) such that
\begin{equation} (sE - A) x = 0, \end{equation}
or \(sE x = Ax\). Because the left side of this equality depends on a variable \(s\), both sides must be zero and \(x\) lies simultaneously in the null space of \(E\) and the null space of \(A\). In this case the associated linear system would have a solution for any value of \(s\).
Additionally, an important property of the regular matrix pencil \((A,E)\) is that the matrix
\begin{equation} \begin{bmatrix} A & E \end{bmatrix} \end{equation}
has full rank. This property is used a couple of times in this thesis.
Standard pencils
The second class of matrix pencils are called standard pencils. A regular matrix pencil \((A,E)\) is a standard pencil if there exists two scalar values \(\mu\) and \(\nu\) such that
\begin{equation} \mu E - \nu A = \eye. \end{equation}
At first this condition may seem very strict, but every regular pencil can be transformed to its standard form~\cite{chang1992generalized}. Take a regular pencil \((A,E)\). Because the pencil is regular, the determinant \(\det(Es-A)\) is not identically zero such that there exists a constant \(\mu\) for which the matrix \(E\mu-A\) is invertible. We now define two new matrices
\begin{equation} \begin{aligned} \bar{E} = (E\mu-A)^{-1}E, \\ \bar{A} = (E\mu-A)^{-1}A. \\ \end{aligned} \end{equation}
The matrix pencil \((\bar{A},\bar{E})\) is a standard pencil because
\begin{equation}\label{eqn:1S-standard-pencil} \bar{E}\mu - \bar{A} = (E\mu-A)^{-1}(E\mu-A) = \eye. \end{equation}
Standard pencils have some nice properties, first and foremost, the matrices in a standard pencil commute. By using Equation~\eqref{eqn:1S-standard-pencil} we have that
\begin{equation} \bar{A} = \bar{E}\mu - \eye. \end{equation}
From this relation it follows that
\begin{equation} \bar{E}\bar{A} = \bar{E}(\bar{E}\mu - \eye) = (\bar{E}\mu - \eye)\bar{E} = \bar{A}\bar{E}. \end{equation}
Commuting matrix pencils
The third class of matrix pencils are commuting matrix pencils. A commuting matrix pencil is a matrix pencil where both system matrices commute. A standard pencil is also a commuting matrix pencil.
Generalized eigenbasis for commuting matrix pencils
We can extend the idea of a commuting matrix pencils, by introducing multiple commuting matrix pencils, where all matrices pairwise commute. In this case, all involved matrices form a commuting matrix family. This set of mutually commuting matrix pencils share a generalized eigenbasis, which is the formulated in the next theorem.
Two regular matrix pencils \((A,E)\) and \((B,F)\) of size \(m\times m\) where all 4 matrices form a commuting family share a generalized eigen basis
\begin{equation} X = \left\lbrace x_1, x_2, \dots, x_m\right\rbrace \end{equation}
Such that all basis vectors \(x_i\) satisfy
\begin{equation} \begin{matrix} (E\lambda_i-A\gamma_i)^{n_i} x_i = 0 \\ (F\mu-B\nu)^{m_i} x_i = 0, \\ \end{matrix} \end{equation}
and
\begin{equation} \begin{matrix} (E\lambda_i-A\gamma_i)^{n_i-1} x_i \neq 0 \\ (F\mu_i-B\nu_i)^{m_i-1} x_i \neq 0 \\ \end{matrix} \end{equation}
for some values \(\lambda_i, \gamma_i, \mu_i\) and \(\nu_i\) and some integers \(n_i\) and \(m_i\).
Due to the pairwise commutation of all four matrices, there exists a basis \(U\) in which \(E,F,A\) and \(B\) are block diagonal matrices. Every block is an upper triangular matrix and has a constant diagonal. Both matrix pencils are transformed to
\begin{equation} \begin{aligned} (\bar{A},\bar{E}) = (U^{-1}AU,U^{-1}EU), \\ (\bar{B},\bar{F}) = (U^{-1}BU,U^{-1}FU). \end{aligned} \end{equation}
such that
\begin{equation} \begin{aligned} \bar{E} = \begin{bmatrix} E_0 & & & \\ & E_1 & & \\ & & \ddots & \\ & & & E_k \\ \end{bmatrix}, & \bar{A} = \begin{bmatrix} A_0 & & & \\ & A_1 & & \\ & & \ddots & \\ & & & A_k \\ \end{bmatrix}, \\ \bar{F} = \begin{bmatrix} F_0 & & & \\ & F_1 & & \\ & & \ddots & \\ & & & F_k \\ \end{bmatrix}, & \bar{B} = \begin{bmatrix} B_0 & & & \\ & B_1 & & \\ & & \ddots & \\ & & & B_k \\ \end{bmatrix}. \\ \end{aligned} \end{equation}
Now consider the matrix pencil \((E_0,A_0)\) which consists of the first blocks of \(\bar{E}\) and \(\bar{A}\). Both matrices have size \(p_0 \times p_0\). Denote the constant diagonal element of \(E_0\) and \(A_0\) respectively by \(\lambda_{0}\) and \(\gamma_{0}\). At least one value of this pair is not equal to zero, otherwise the matrix pencil \((A,E)\) would not be regular. We now define the new matrix \(D_0 = E_0\gamma_0 - A_0\lambda_0\) as the weighted difference between both matrices. The matrix \(D_0\) is an upper triangular matrix with zero on the diagonal. This implies that \(D_0\) only has the eigenvalue zero, which makes it a nilpotent matrix and thus, there exists a positive integer \(p\) such that \(D_0^p=0\) and \(D_0^{p-1}\neq 0\).
Take a random vector \(x\) and define \(v_1 = D_0x\). The vector \(v_1\) can now either be zero or it is not. If \(v_1\) is zero, than we have proven that
\begin{equation} (E_0\gamma_0 - A_0\lambda_0) x = 0. \end{equation}
If \(v_1\) is not zero we introduce a second vector \(v_2 = D_0^2x\). Because of the nilpotency of \(D_0\) there will always exist a power \(k\) such that \(D_0^kx=0\), where \(k\) is bound by the nilpotency index.
The same analysis can now be carried out for the matrix pencil \((F_0,B_0)\). The constant diagonal element of \(F_0\) and \(B_0\) is respectively denoted by \(\nu_0\) and \(\mu_0\). Define \(C_0 = F_0\mu_0 - B_0\nu_0\) as the weighted difference. This matrix is again a nilpotent matrix and there exists a positive integer \(l\) such that \(c_0^lx=0\) and \(c_0^{l-1}x\neq0\).
This procedure can be repeated to generate \(p_0\) linearly independent vectors which form a basis and satisfy the aforementioned conditions. Every vector \(x\) only has a size of \(m_i\), equal to the number of rows/columns of \(A_0\) and has to be extended by trailing zeros in order to make the vector the same size as the original matrix pencil.
The full basis is than obtained by further repeating the calculations for all pairs of \((A_i,E_i)\) and \((B_i,F_i)\) of pencils formed by the diagonal blocks.
Conclusions
This short chapter very briefly touches only a few subjects of linear algebra. All presented concepts are further elaborated on in the next chapters.