3.12    Best Approximations and Orthogonal Projections

The following result plays an important role in many signal processing applications involving estimation and optimization tasks such as solving an overdetermined system of equations in the least-squares (LS) sense [10, 11].

Theorem 3.12.1. (Orthogonal Projection Theorem [6]) Let $\mathcal{V}$ be an inner-product vector space and let $\mathcal{S}$ be a subspace of it. For every vector v ∈ $\mathcal{V}$ there may exist a best approximation s ∈ $\mathcal{S}$ such that

$\Vert v-s\Vert \le \Vert v-s^{\prime }\Vert ,\forall s^{\prime }\in \mathcal{S}.$

(3.100)

This condition holds if and only if

$\left(v-s\right)\perp s^{\prime },\forall s^{\prime }\in \mathcal{S}.$

(3.101)

Moreover, if this best approximation exists, then it is unique. Now let an orthogonal basis for $\mathcal{S}$ be denoted by {s₁, s₂,…, s_m}. It can be shown that the best approximation of v by vectors in $\mathcal{S}$ can be computed as

$s={\displaystyle \sum _{k=1}^m\frac{\langle v|s_k\rangle }{{\Vert s_k\Vert }^2}{s}_k}.$

(3.102)

In other words, the best approximation of v by vectors in $\mathcal{S}$ is given by the orthogonal projection s of vector v onto the subspace $\mathcal{S}$. Notice further that in (3.102), the k^th term in the sum is the projection of v on the direction of vector s_k. Consider now that for any vector v ∈ $\mathcal{V}$, there exists an orthogonal projection onto subspace $\mathcal{S}$. Thus, a mapping P : $\mathcal{V}$ → $\mathcal{S}$ can be defined that associates to each v ∈ $\mathcal{V}$, its orthogonal projection onto $\mathcal{S}$. Mapping P will be referred to as the orthogonal projection of $\mathcal{V}$ onto subspace $\mathcal{S}$, and some of its properties will be considered in Exercise 3.23.18.

3.13    Least Squares Approximations

Suppose T : $\mathcal{V}$ → $\mathcal{W}$ is a linear transformation such that for some v ∈ $\mathcal{V}$ and w ∈ $\mathcal{W}$, the equation

$T\left(v\right)=w$

(3.103)

does not present an exact solution; i.e., w does not lie in the range space of T. In practice, such equations are often encountered and solutions that satisfy (3.103) in an approximative manner must be determined. One of the most common approaches adopted for solving (3.103) is to find a vector v such that the norm of the least-squares (LS) criterion:

$e={\Vert T\left(v\right)-w\Vert }^2,$

is minimized. This problem reduces to finding the vector w′ ∈ $\mathcal{R}$(T) such that

$T\left(v\right)=w^{\prime },$

(3.104)

and ‖w′ - w‖ is minimized. The corresponding solution v of (3.104) is called the least squares solution. The following result characterizes the LS solution of (3.103) (see e.g., [6, 8]).

Theorem 3.13.1. Vector v ∈ $\mathcal{V}$ is the minimizer of ‖T(v) - w‖ if and only if

$T^{*}T\left(v\right)=T^{*}\left(w\right).$

(3.105)

If T^*T is invertible, then the LS solution is unique and given by:

$v={\left(T^{*}T\right)}^{-1}{T}^{*}\left(w\right),$

(3.106)

and

$w^{\prime }=T\left(v\right)=T{\left(T^{*}T\right)}^{-1}{T}^{*}\left(w\right).$

(3.107)

A justification of this result is delegated to Exercise 3.23.20.

Now consider the inconsistent overdetermined m × n(m > n) system of linear equations Av = w. If w does not lie in the column space ($\mathcal{R}$(A)), there is no exact solution. Using the LS method, a unique vector ŵ ∈ $\mathcal{R}$(A) that is closest to w can be found; or equivalently we can choose v̂ to minimize the norm of the error ‖Av̂−w‖ Finding the least squares solution v̂ is equivalent to finding

$\widehat{w}=A\widehat{v},$

(3.108)

that is closest to w than any other vector in the column space $\mathcal{R}$(A). Any solution to the new system of equations:

$Av=\widehat{w}$

(3.109)

is referred to as a least-squares solution for Av = w. Finally, note that the least-squares solution to Av = w is any vector v that minimizes ‖ Av −w‖The following result characterizes the LS solution of minimum norm for an overdetermined system of linear equations [3, 6, 8].

Theorem 3.13.2. If A is an m x n matrix (m ≥ n) and A* A is invertible, then among all the least squares solutions of the system of equations: Av = w, there is a unique LS solution of minimum norm given by:

$v={\left(A^{*}A\right)}^{-1}{A}^{*}w.$

(3.110)

The matrix (A*A)⁻¹A* is called the Moore-Penrose pseudoinverse of A. The approximation ŵ of w by the vectors in $\mathcal{R}$(A) is given by:

$\widehat{w}=Av=A{\left(A^{*}A\right)}^{-1}{A}^{*}w,$

(3.111)

and it is obtained by projecting w onto $\mathcal{R}$(A). As a corollary, the error term w – ŵ is orthogonal to $\mathcal{R}$(A). Reference [3] presents several extensions of these results and a characterization of all the LS solutions.

3.14    Angles Between Subspaces

3.14.1    Principal Angles Between Subspaces

Recall that given two non-zero vectors v, w ∈ ℝⁿ, the angle between them is computed as

$\theta =co{s}^{-1}\frac{\langle v|w\rangle }{\Vert v\Vert \cdot \Vert w\Vert },\text{}\left(0\le \theta \le \raisebox{1ex}{$\pi $}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right).$

(3.112)

Now suppose that we are given two subspaces represented in terms of the range spaces of two matrices A and B. A set of angles between them can be defined recursively. These angles will be referred to as principal (canonical) angles. Matrices A and B are assumed real-valued with the same number n of rows and dim $\mathcal{R}$(A) = p and dim $\mathcal{R}$(B) = q(q ≥ p). The principal angles θ₁, θ₂, …, θ_q ∈ [0, ^π/2] between the two column spaces $\mathcal{R}$(A) and $\mathcal{R}$(B) are recursively defined via:

$\begin{array}{c}cos\left({\theta }_k\right)=\underset{v\in ℛ\left(A\right)}{\max }\underset{w\in ℛ\left(B\right)}{\max }{v}^{T}w\\ =v_k^T{w}_k,k=1,\dots ,q,\end{array}$

subject to these conditions: ‖v‖ = ‖w‖ = 1, v^Tv_i = 0, w^Tw_i; =0, i = 1,…, k −1. Notice that the notation ‖·‖ stands for the standard Euclidean norm of a vector, and the resulting vectors v_i’s and w_i’s are called the principal vectors. Notice also that during step k, the algorithm determines θ_k, and the associated principal vectors v_k and w_k by searching for vectors in subspaces that are orthogonal with respect to v_i and w_i, i = 1,…, k − 1, respectively. Therefore, by searching for vectors that present the largest angle between them and that are orthogonal to the already found principal vectors, the complete sets of principal angles and principal vectors are obtained.

The concept of principal angles between two vector spaces has found applications in assessing the degree of correlation between two sets of random variables and has been used in canonical analysis [13, 14]. Applications of principal angles also include random processes [15, 16], stochastic realization of random processes and system identification [17, 18, 19], pattern recognition and machine learning (see e.g., [20, 21]), and signal processing and communications (see e.g., the signal estimation and detection applications presented in [22]).

3.15    Eigenvalues and Eigenvectors

Let T be a linear operator on a vector space $\mathcal{V}$, T : $\mathcal{V}$ → $\mathcal{V}$. An eigenvalue of T is a scalar λ such that

$T\left(v\right)=\text{λ}v,$

(3.113)

for a non-zero vector v ∈ $\mathcal{V}$. The vector v is called an eigenvector of T. Similarly, for an n × n matrix A that is the matrix representation of the linear transformation T, an eigenvalue is a scalar λ that makes the matrix A − λI singular. The eigenvector of matrix A corresponding to eigenvalue λ is any non-zero vector v that satisfies the equation Av = λν. The polynomial in λ expressed as:

${\chi }_A\left(\text{λ}\right)=\det \left(A-\text{λ}I\right),$

(3.114)

is called the characteristic polynomial of A and the equation

$\det \left(A-\text{λ}I\right)=0,$

(3.115)

is referred to as the characteristic equation of A. The set of roots of the characteristic equation provides the set of eigenvalues, and therefore, it is also referred to as the spectrum of A and denoted by the notation by σ(A). Thus, every eigenvalue λ is a root of the characteristic polynomial. The eigenspace corresponding to an eigenvalue λ of A is defined as the subspace

$E_{\text{λ}}=\left\{v\in \mathcal{V}|Av=\text{λ}v\right\}.$

(3.116)

If A has distinct eigenvalues, the eigenspaces are all one-dimensional. The following general results, whose proofs are deferred to Exercises 3.23.22 and 3.23.23, hold.

Theorem 3.15.1. Let A be an n × n matrix with distinct eigenvalues. Then, the eigenvectors of A form a linearly independent set.

Theorem 3.15.2. The eigenvectors of a Hermitian matrix are real and the eigenvectors corresponding to distinct eigenvalues are orthogonal.

The concepts of eigenvalue and eigenvector play an important role in building high-resolution spectral estimation techniques, designing efficient algorithms for localization and tracking in antenna array processing [12], checking stability of digital filters, system identification, designing efficient signaling schemes in multiantenna (multi–input multi–output (MIMO)) based communication systems [25], etc.

3.15.1    Diagonalization

A square matrix A is diagonalizable if it can be factored as follows:

$A=S\text{Λ}{S}^{-1},$

(3.117)

for some non-singular matrix S and diagonal matrix Λ. Notice that Λ presents the same eigenvalues as A. In general, two matrices A and Λ that are related by means of an equation of the form (3.117) are referred to as similar matrices,and they present the same set of eigenvalues. The following result provides an alternative characterization for diagonalizable matrices.

Theorem 3.15.3. If A is an n × n matrix, then it is diagonalizable if it admits n linearly independent eigenvectors or n distinct eigenvalues.

A justification of this result is left to Exercise 3.23.23.

Using the characteristic function, it can be checked that the eigenvalues of a diagonal matrix coincides with its diagonal entries. Also, it is not difficult to show that the i^th column of S is actually the eigenvector of A corresponding to the i^th diagonal entry (eigenvalue) of Λ (A), for any i = 1,… ,n. The following result shows a simple way to calculate the higher order powers of a matrix in terms of the higher-order powers of its eigenvalues.

Theorem 3.15.4. Let A be an n × n matrix with eigenvalues λ₁,…, λ_n. Then the eigenvalues of A^k (k∈ ℤ) are ${\text{λ}}_1^k,\dots ,{\text{λ}}_n^k$. Moreover, it follows that

$\begin{array}{l}{A}^k={\left(S\text{Λ}{S}^{-1}\right)}^k\\ =S{\text{Λ}}^k{S}^{-1}.\end{array}$

(3.118)

3.16    Schur Factorization and Spectral Theorem

Theorem 3.16.1. Let A be an n × n matrix. There exists a unitary matrix Q such that the multiplication

$T=Q^{†}AQ$

(3.119)

is upper triangular, or equivalently A can be factorized as

$A=QT{Q}^{†},$

(3.120)

where T is an upper triangular matrix.

The decomposition (3.120) is referred to as Schur’s factorization. Notice that the diagonal elements of T consist of the eigenvalues of A. The proof of this theorem can be done using the induction principle with respect to n. Alternative justifications for Schur factorization can be found in [3, 5, 24].

Theorem 3.16.2. (Spectral Theorem) For any Hermitian matrix A, there is a unitary diagonalizing matrix Q.

Stated differently, if A is a Hermitian matrix, the matrix T in Schur’s factorization must be diagonal. Assume there exists a unitary matrix Q such that (3.119) holds, where T is an upper triangular matrix. However, A^† = A, because A is Hermitian symmetric. Hence, T^† = Q^†A^†Q = Q^†AQ = T, Thus, T is also Hermitian symmetric. Being also an upper triangular matrix, T should be diagonal. As an immediate corollary, if A is a real-valued symmetric matrix, then it can be diagonalized via an orthogonal matrix Q, i.e., the equality Q^TAQ = T holds. Since Q is diagonalizing A to T, the diagonal elements of T are the eigenvalues of A, and the columns of Q consist of eigenvectors of A, i.e., A = QTQ^T represents the spectral decomposition of a symmetric matrix.

3.17    Singular Value Decomposition (SVD)

Let A be an m × n real-valued matrix. Then the Singular Value Decomposition (SVD) of matrix A is given by the factorization [24]:

$A=U\text{Σ}{V}^T,$

(3.121)

where Σ is an m × n diagonal matrix, and U and V are two orthogonal matrices of dimensions m × m and n × n, respectively. In general, Σ can be expressed as

$\text{Σ}=\left[\begin{array}{cc}{\text{Σ}}^{\prime }& 0_{r\times \left(n-r\right)}\\ 0_{\left(m-r\right)\times r}& 0_{\left(m-r\right)\times \left(n-r\right)}\end{array}\right],$

(3.122)

where

${\text{Σ}}^{\prime }={\left[\begin{array}{cccc}{\sigma }_1& 0& \cdots & 0\\ 0& {\sigma }_2& \ddots & ⋮\\ ⋮& \ddots & \ddots & 0\\ 0& \cdots & 0& {\sigma }_r\end{array}\right]}_{r\times r}{\sigma }_i>0,1\le i<r,$

(3.123)

and r stands for the rank of matrix A. The non-zero entries on the main diagonal of Σ, σ_i, i = 1,…r, are non-negative and are referred to as the singular values of A. Notice that using (3.121), it follows that AA^T =UΣΣ^TU^T and A^TA =VΣ^TΣV^T Because matrices U and V are orthogonal, and ΣΣ^T and Σ^T Σ are diagonal, it follows that the singular values of matrix A are equal with the square roots of non-zero eigenvalues of A^†A and AA^†. Furthermore, the columns of U and V are the eigenvectors of AA^T and A^TA, respectively. The SVD holds also for complex-valued matrices. If A is a complex-valued matrix, then its SVD assumes the factorization: A = UΣV^†, where U and V are unitary matrices and Σ is a diagonal matrix with nonnegative entries. Although in the SVD factorization, σ₁,…,σ_r are unique, U and V are not.

The SVD (3.121) can be re-expressed in these two alternative ways:

$AV=U\text{Σ},$

(3.124)

and

$A^{T}U=V{\text{Σ}}^T.$

(3.125)

Equating the i^th columns in the left-hand-side (LHS) and right-hand side (RHS) of (3.124) and (3.125), it follows that:

$A{v}_i={\sigma }_i{u}_{i}i=1,2,\dots ,r,$

(3.126)

and

$A^T{u}_i=\{\begin{array}{ll}{\sigma }_i{v}_i\hfill & 1\le i\le r\hfill \\ 0\hfill & r+1\le i\le m\hfill \end{array},$

(3.127)

where vectors u_i and v_i stand for the ith column of matrices U and V, respectively. Vectors v_i ’s and u_i ’s are called right singular vectors and left singular vectors of A, respectively. It follows also that {v₁, v₂,…, v_r} and {u₁, u₂,…, u_r} represent orthogonal bases for $\mathcal{R}$(A^T) and $\mathcal{R}$(A), respectively. Likewise, {v_r+1, v_r+2,…, v_n} and {u_r+1, u_r+2,…, u_r} are orthogonal bases for $\mathcal{N}$ull (A) and $\mathcal{N}$ull (A^T), respectively. Thus, the SVD provides bases for all the four fundamental subspaces of a matrix: $\mathcal{R}$(A), $\mathcal{N}$ull (A), $\mathcal{R}$(A)^⊥, and $\mathcal{N}$ull (A)^⊥. Notice also that the rank r of A is obtained immediately from its SVD, and it is equal to the number of non-zero entries located on the main diagonal of Σ. SVD enables also the construction of the orthogonal projections on the four fundamental subspaces of a matrix. E.g., if matrices U_1:r and V_1:r stand for the sub-matrices formed by the columns 1 through r of matrices U and V, respectively, then ${\mathrm{U}}_{1:r}{\mathrm{U}}_{1:r}^T$ and $V_{1:r}{V}_{1:r}^T$ represent the orthogonal projection matrices on R(A) and $\mathcal{N}$ull (A)^⊥ , respectively [3, 24].

Reference [24] presents a number of applications of SVD in calculating row-rank matrix approximations, principal angles between subspaces, generalized inverses, solving systems of equations in the standard or total least-squares sense, orthogonal projections, etc. During the past decades, SVD proved to be a powerful tool in solving numerous problems in statistics, signal processing, wireless communications, information theory, pattern recognition, machine learning and other fields. Also, SVD played an important role in enabling the calculation of the capacity of a MIMO channel by reducing the MIMO channel to a number of independent single–input single–output (SISO) channels [25], developing efficient high-resolution spectral estimation techniques [12], and designing optimal channel estimation, signaling and equalization techniques.

3.18    Rayleigh Quotient

Suppose A is an n × n Hermitian matrix, and denote by λ₁ ≥ λ₂ ≥…≥ λ_n and u₁, u₂,…, u_n its eigenvalues and corresponding orthogonal eigenvectors, respectively. Notice also that the Spectral Theorem 3.16.2 guarantees the existence of a factorization of the form A = UΛU^H, with U unitary and Λ diagonal matrix containing on its main diagonal the eigenvalues of A. One can observe that orthonormal vectors u₁, u₂,…, u_n, representing the columns of U, stand also for the eigenvectors of A corresponding to eigenvalues λ₁,…, λ_n. If x is a non-zero vector in Cⁿ, then the Rayleigh quotient of x with respect to Hermitian matrix A is defined as:

$R\left(x\right)=\frac{\langle Ax|x\rangle }{\langle x|x\rangle }=\frac{x^{†}Ax}{x^{†}x}.$

(3.128)

It can be shown that the minimum and the maximum values of the Rayleigh quotient are λ_n and λ₁, respectively, i.e.,

${\text{λ}}_n\le R\left(x\right)\le {\text{λ}}_1.$

(3.129)

A quick justification of (3.129) can be obtained by expressing the arbitrary vector x ∈ ℂⁿ as a linear combination of the orthogonal eigenvectors of A, u_i, i = 1,…, n (or in terms of the singular vectors of A obtained via SVD),

$x={\displaystyle \sum _{i=1}^n{a}_i{u}_i}.$

(3.130)

Plugging3.130 into3.128, it follows that:

$\begin{array}{c}R\left(x\right)=\frac{{\displaystyle {\sum }_{i=1}^n{\text{λ}}_i{\left|a_i\right|}^2}}{{\displaystyle {\sum }_{i=1}^n{\left|a_i\right|}^2}}\\ =\frac{{\displaystyle {\sum }_{i=1}^n{\text{λ}}_i{\left|a_i\right|}^2}}{{\Vert \mathrm{a}\Vert }_2^2},\end{array}$

(3.131)

where a = [a₁, a₂,…,a_n]^T. Because of the ordering λ₁ ≥ λ₂ ≥…≥ λ_n, it follows that the numerator in (3.131) can be lower- and upper-bounded, respectively, by:

${\text{λ}}_n{\Vert \mathrm{a}\Vert }_2^2\le {\displaystyle \sum _{i=1}^n{\text{λ}}_i{\left|a_i\right|}^2\le {\text{λ}}_1{\Vert \mathrm{a}\Vert }_2^2},$

from where (3.129) follows immediately. Rayleigh quotient found applicability in signal processing and wireless communication applications dealing with the design of filters and equalization schemes with improved performance.

3.19    Application of SVD and Rayleigh Quotient: Principal Component Analysis

Suppose we have an m × n (m ≥ n) matrix X of rank r, and whose column vectors are possibly correlated (i.e., are not orthogonal). The principal component analysis (PCA) is a method that transforms a set of correlated variables (in this case column vectors of matrix X) into a possibly smaller set of uncorrelated variables {y₁,… y_r}, called principal components vectors, that present the largest possible norm (variance, power or variability) and span the same vector space as the column space of matrix X. Herein application, the “uncorrelatedness” condition is achieved by imposing that the vectors y_i’s, i = 1, 2,… r, are orthogonal.

Consider now the SVD (or spectral) decomposition of correlation matrix C = X^TX/(n − 1) under the form C = UΛU^T, where Λ is a diagonal matrix with the diagonal entries λ₁ ≥ λ₂ ≥ … ≥ λ_r > 0, and U = [u₁, u₂,…, u_n] is anorthogonal matrix. The facts that y_i’s must lie in the range space of X and must be uncorrelated imply that at most r principal component vectors might be defined. Next we will determine the first principal component y₁ as the vector of largest variance or norm that lies in the range space of matrix X. This reduces to finding the vector y₁ = Xv₁, where v₁ is an arbitrary vector of unit norm, such that

$Var\left(y_1\right)=\frac{y_1^T{y}_1}{n-1}=\frac{{\left(X{v}_1\right)}^{T}X{v}_1}{n-1}=v_1^{T}C{v}_1,$

(3.132)

is maximized. The Rayleigh quotient implies immediately that v₁ should coincide with the eigenvector (u₁) corresponding to the largest eigenvalue (λ₁) of correlation matrix C. Now, using the Induction Principle, we will construct the remaining principal directions. Assuming that the first k− 1 principal component vectors y₁,…, y_k−1 are given by the eigenvectors u₁,…, u_k−1 corresponding to the first k − 1 largest eigenvalues, respectively, we want to prove that the kth principal component vector is given by the eigenvector u_k corresponding to the kth eigenvalue λ_k. Consider that y_k = Xv_k, where v_k is an arbitrary vector of unit norm. Because y_k should be orthogonal to y₁,…, y_k−1, it follows that

$y_k^{T}y\iota =0,\forall l=1,\dots ,k-1.$

(3.133)

Equation (3.133) leads further to

$\left(v_k^T{X}^T\right)\left(Xu\iota \right)=\left(n-1\right)v_k^{T}Cu\iota =\left(n-1\right){\text{λ}}_{\iota }{v}_k^{T}u\iota =0,\forall l=1,\dots ,k-1$

(3.134)

Thus, it follows that necessarily v_k should lie in the range space of orthogonal eigenvectors u_k,…, u_n. Consequently, there exist the scalars α_l, l = k,…,n,such that:

$v_k={\displaystyle \sum _{l=k}^n{\alpha }_{\iota }{u}_{\iota }},$

(3.135)

and ${\displaystyle {\sum }_{l=k}^n{\alpha }_l^2}=1$ is imposed to enforce the unit norm for v_k. Notice that the maximization of the kth principal component norm or variance is equivalent to the maximization of

$y_k^T{y}_k={\left({\displaystyle \sum _{j=k}^n{\alpha }_j{u}_j}\right)}^T{X}^{T}X\left({\displaystyle \sum _{l=k}^n{\alpha }_{\iota }{u}_{\iota }}\right)={\displaystyle \sum _{l=k}^n{\alpha }_{\iota }^2{\text{λ}}_{\iota }^2},$

(3.136)

with respect to scalars αι, l = k,…, n, and assuming the constraint ${\displaystyle {\sum }_{l=k}^n{\alpha }_l^2}=1$. Obviously, the maximum of (3.136) is achieved when αι = 0 for l > k, and |α_k | = 1. This concludes the proof. In other words, the eigenvectors corresponding to the correlation matrix C yield the principal component directions. Depending on the applications where the PCA method is employed, PCA undertakes different names such as Karhunen-Loeve transformation, SVD or Hotelling transform. For more details on PCA, the reference [25] presents a comprehensive overview of PCA and its applications.

3.20    Special Matrices

In this section several special matrices such as block, circulant, Toeplitz, Vandermonde, stochastic, generalized inverse and positive definite matrices will be introduced.

3.20.1    Block Matrices

A matrix A is referred to as a block matrix if it can be represented in terms of sub-matrices A_i,j of appropriate sizes as follows:

$A=\left[\begin{array}{cccc}{A}_{1,1}& A_{1,2}& \dots & A_{1,n}\\ A_{2,1}& A_{2,2}& \dots & A_{2,n}\\ ⋮& ⋮& \ddots & ⋮\\ A_{m,1}& A_{m,2}& \dots & A_{m,n}\end{array}\right].$

(3.137)

A block matrix with non-zero entries on its main diagonal and zero-blocks elsewhere is called a block diagonal matrix, and assumes the expression:

$A=\left[\begin{array}{ccc}{A}_1& \dots & 0\\ ⋮& \ddots & ⋮\\ 0& \dots & A_n\end{array}\right].$

Some properties pertaining to the multiplication of two block matrices A and B of appropriate sizes are listed below.

•  If $\mathrm{A}=\left[\begin{array}{c}{\mathrm{A}}_1\\ {\mathrm{A}}_2\end{array}\right]$, then $\mathrm{AB}=\left[\begin{array}{c}{\mathrm{A}}_1\mathrm{B}\\ {\mathrm{A}}_2\mathrm{B}\end{array}\right]$

•  If B = [B₁ B₂ ] , then A [ B₁ B₂ ] = [ AB₁ AB₂].

•  if $\mathrm{A}=\left[\begin{array}{c}{\mathrm{A}}_1\\ {\mathrm{A}}_2\end{array}\right],\mathrm{B}=\left[{\mathrm{B}}_1,{\mathrm{B}}_2\right]$, the $\mathrm{AB}=\left[\begin{array}{c}{\mathrm{A}}_1\\ {\mathrm{A}}_2\end{array}\right]\left[{\mathrm{B}}_1,{\mathrm{B}}_2\right]=\left[\begin{array}{c}{\mathrm{A}}_1{\mathrm{B}}_1{\mathrm{A}}_1{\mathrm{B}}_2\\ {\mathrm{A}}_2{\mathrm{B}}_1{\mathrm{A}}_2{\mathrm{B}}_2\end{array}\right]$

•  If $\mathrm{A}=\left[\begin{array}{c}{\mathrm{A}}_{1,1}{\mathrm{A}}_{1,2}\\ {\mathrm{A}}_{2,1}{\mathrm{A}}_{2,2}\end{array}\right]\mathrm{B}=\left[\begin{array}{c}{\mathrm{B}}_{1,1}{\mathrm{B}}_{1,2}\\ {\mathrm{B}}_{2,1}{\mathrm{B}}_{2,2}\end{array}\right]$, then $\mathrm{AB}=\left[\begin{array}{c}{\mathrm{A}}_{1,1}{\mathrm{B}}_{1,1}+{\mathrm{A}}_{1,2}{\mathrm{B}}_{2,1}{\mathrm{A}}_{1,1}{\mathrm{B}}_{1,2}+{\mathrm{A}}_{1,2}{\mathrm{B}}_{2,2}\\ {\mathrm{A}}_{2,1}{\mathrm{B}}_{1,1}+{\mathrm{A}}_{2,2}{\mathrm{B}}_{2,1}{\mathrm{A}}_{2,1}{\mathrm{B}}_{1,2}+{\mathrm{A}}_{2,2}{\mathrm{B}}_{2,2}\end{array}\right]$

The proof of the last property is delegated to Exercise 3.23.25. Reference [7] presents additional properties of block matrices.

3.20.2    Circulant Matrices

An n × n matrix A is called circulant if each row of A is obtained by right-shifting the previous row by one column, and the element in the last column being shifted to the first column. In other words, a circulant matrix can be defined in terms of elements located on its first row, as depicted below:

$A=circ\left(a_1,\dots ,a_n\right)=\left[\begin{array}{lllllllll}{a}_1\hfill & \hfill & a_2\hfill & \hfill & \dots \hfill & \hfill & a_{n-1}\hfill & \hfill & a_n\hfill \\ \hfill & \searrow \hfill & \hfill & \searrow \hfill & \hfill & \searrow \hfill & \hfill & \searrow \hfill & \hfill \\ a_n\hfill & \hfill & a{}_1\hfill & \hfill & \dots \hfill & \hfill & a_{n-2}\hfill & \hfill & a_{n-1}\hfill \\ ⋮\hfill & \hfill & ⋮\hfill & \hfill & \hfill & \hfill & ⋮\hfill & \hfill & ⋮\hfill \\ \hfill & \searrow \hfill & \hfill & \hfill & \hfill & \searrow \hfill & \hfill & \searrow \hfill & \hfill \\ a_2\hfill & \hfill & a_3\hfill & \hfill & \dots \hfill & \hfill & a_n\hfill & \hfill & a_1\hfill \end{array}\right].$

(3.138)

The circularity condition for matrix A = [a_k,l] can be described alternatively through the condition:

$a_{k,l}=\{\begin{array}{ll}{a}_{k-1,l-1}\hfill & k=2,\dots ,n,l=2,\dots ,n\hfill \\ a_{k-1,n}\hfill & k=2,\dots ,n,l=1\hfill \end{array}.$

Consider now two circulant matrices A and B of the same size and arbitrary scalars α and β. Then the following statements hold:

•  A^T is circulant.

•  αA + βB is circulant.

•  A^k is circulant, for any positive integer k.

•  If A is nonsingular, then A⁻¹ is circulant.

•  AB is circulant.

The proofs of the last two properties are delegated to Exercise 3.23.27.

An important feature of circulant matrices is that they can be diagonalized using Discrete Fourier Transform (DFT). In fact, for an arbitrary n × n circulant matrix A the following spectral decomposition holds:

$A=F_n^{*}{\text{Λ}}_n{F}_n,$

(3.139)

where F_n is the DFT matrix with entries

${\left[F_n\right]}_{k,l}=\frac{1}{\sqrt{n}}{e}^{-2\pi \sqrt{-1}kl/n},0\le k,l\le n-1,$

and Λ_n is a diagonal matrix with its diagonal entries equal to the eigenvalues of matrix A. The diagonal entries of Λ_n, i.e., the eigenvalues of circulant matrix A, can be calculated in O(n log n) flops (floating point operations) by considering the fast Fourier transform (FFT) of the first column of A. Indeed, using (3.139) and denoting by 1 the vector of all ones and e₁ = (1, 0,…, 0)^T, the following equations hold:

$\begin{array}{c}{\text{Λ}}_n{F}_n=F_{n}A,\\ {\text{Λ}}_n{F}_n{e}_1=F_{n}A{e}_1,\\ {\text{Λ}}_{n}1=F_{n}A{e}_1,\end{array}$

(3.140)

where we took into consideration in (3.140) the fact that F_ne₁ = 1. Equating the k entries in the LHS and RHS of (3.140), it follows that the diagonal entries λ_k of Λ_n are given by

${\text{λ}}_k=\frac{1}{\sqrt{n}}{\displaystyle \sum _{j=0}^{n-1}{a}_j{e}^{-2\pi ijk/n}},k=0,\dots ,n-1,i=\sqrt{-1}$

Exercise 3.23.28 describes how the eigenvectors of circulant matrix A can be efficiently determined. Circular matrices are important in signal processing applications because they arise in the matrix representation of circular convolution between two discrete-time sequences (see e.g., [26]). Since the inverse DFT of the product of two DFTs is equal to the circular convolution of the two sequences whose DFTs are multiplied, circular matrices play a fundamental role in performing the linear convolution between two sequences [26]. Reference [27] presents a nice introduction to circular matrices. Additional properties of circular matrices can be found in [7].

3.20.3    Toeplitz Matrices

An n × n matrix A = [a_k,l] whose entries satisfy the property a_k,l = a_k−l is called a Toeplitz matrix. In other words, the entry (k, l) of a Toeplitz matrix is perfectly described by the difference between its row and column indices. Due to this fact, the following well-known characterization of Toeplitz matrices is used in the literature: all matrix entries located on diagonals parallel with the main diagonal are equal. As a corollary, all Toeplitz matrices are perfectly determined by its first column and first row vectors. Notice also that circulant matrices are a special class of Toeplitz matrices. Toeplitz matrices are present in the representation of discrete-time linear convolutions between two sequences, and autocorrelation (auto-covariance) matrices of stationary stochastic processes. An interesting and quite useful property of Toeplitz matrices is the fact that Toeplitz systems of equations of the form Ax = b can be solved efficiently in O(n²) flops using the Levinson-Durbin algorithm. This result plays an important role in designing parametric autoregressive-moving average (ARMA) or AR power spectral density estimators (solving the Yule-Walker system of equations) [12], calculation of Wiener (minimum mean-square error (MMSE)) equalizers and predictors. For additional information, reference [27] represents an excellent elementary introduction to Toeplitz and circulant matrices.

3.20.4    Hankel Matrices

A matrix A = [a_k,l] whose entries satisfy the condition: a_k,l = a_k+l is referred to as a Hankel matrix. Hankel matrices enjoy the property that the entries located on anti-diagonals are equal. Therefore, the entries of a Hankel matrix are perfectly described by its first row and last column. Hankel matrices found applicability in the design of state-space based system identification and channel estimation algorithms [28]. Hankel matrices enjoy similar properties to Toeplitz matrices in terms of computing their inverses. This can be understood by noticing the result: if J stands for the exchange matrix, i.e., the matrix with all the entries on the main counter-diagonal equal to 1 and with zeros elsewhere, then JA is Toeplitz for a square Hankel matrix A [7].

3.20.5    Vandermonde Matrices

A Vandermonde matrix A admits the following structure:

$A=\left[\begin{array}{lllll}1\hfill & a_1\hfill & a_1^2\hfill & \dots \hfill & a_1^{m-1}\hfill \\ 1\hfill & a_2\hfill & a_2^2\hfill & \dots \hfill & a_2^{m-1}\hfill \\ ⋮\hfill & ⋮\hfill & ⋮\hfill & \hfill & ⋮\hfill \\ 1\hfill & a_m\hfill & a_m^2\hfill & \dots \hfill & a_m^{m-1}\hfill \end{array}\right]$

(3.141)

$={\left[\begin{array}{llll}1\hfill & 1\hfill & \dots \hfill & 1\hfill \\ a_1\hfill & a_2\hfill & \dots \hfill & a_m\hfill \\ a_1^2\hfill & a_2^2\hfill & \dots \hfill & a_m^2\hfill \\ a_1^{m-1}\hfill & a_2^{m-1}\hfill & \dots \hfill & a_m^{m-1}\hfill \\ \hfill & \hfill & \hfill & \hfill \end{array}\right]}^T$

(3.142)

In other words, in each row in a Vandermonde matrix are terms of a geometric progression. A square Vandermonde matrix A enjoys the property that its determinant can be expressed in closed-form expression:

$\det \left(A\right)={\displaystyle \prod _{1\le i\le j\le m}\left(a_j-a_i\right)}.$

(3.143)

Vandermonde matrices arise in applications involving evaluations of polynomials at a specific set of values, polynomial least-squares fitting and polynomial interpolation designs.

3.20.6    Normal Matrices

A complex square matrix A is said to be a normal if

$A^{†}A=A{A}^{†},$

where we recall that superscript. ^†stands for the conjugate transposition (Hermitian transposition) operation. For real-valued matrices, a normal matrix satisfies the condition:

$A^{T}A=A{A}^T.$

One of the most important features of normal matrices is the fact that they are unitarily diagonalizable, i.e., there exists a unitary matrix U such that U^HAU = diag(λ₁,…, λ_n) [5]. In particular, notice that a Hermitian symmetric (or antisymmetric) matrix is a normal matrix.

3.20.7    Stochastic Matrices

An n × n matrix A = [α_k,l] is called stochastic (probabilistic or transition) matrix if all its entries are non-negative (a_k,l ≥ 0) and the entries in each row add up to one ${\displaystyle {\sum }_{l=1}^n{a}_{k,l}}=1$ A stochastic matrix can be interpreted as the transition probability matrix in a Markov chain, and its use arises in many fields such as probability, statistics, computer science, optimization (majorization theory), etc. A matrix with non-negative entries and with each column summing up to one is also referred to as a stochastic matrix. A doubly stochastic matrix is a matrix with non-negative entries, and in which each row and each column add up to one.

3.20.8    Positive and Negative Definite Matrices

Assume x is an n × 1 vector in ℝⁿ and n × n matrix A is symmetric. The quadratic form f (x) = x^TAx is said to be positive (negative) definite if f (x) > 0 (f (x) < 0) for any non-zero vector x. By definition, the real symmetric matrix A is called:

•  Positive Definite iff x^TAx > 0 , ∀x ∈ ℝⁿ − {0}.

•  Positive Semi-Definite iff x^TAx ≥ 0 , ∀x ∈ ℝⁿ − {0}.

•  Negative Definite iff x^TAx < 0 , ∀x ∈ ℝⁿ − {0}.

•  Negative Semi-Definite iff x^T Ax ≤ 0 , ∀x ∈ ℝⁿ − {0}.

The following result provides an alternative way to assess when a matrix is positive definite.

Theorem 3.20.1. A real symmetric matrix A is positive definite if and only if all of its eigenvalues are positive.

The proof of this result is left to Exercise 3.23.30. An alternative method to check for the positive definiteness of a matrix is to verify that the determinants of all principal submatrices are all positive (see e.g., [8]). Additional information about the properties and applications of positive definite matrices can be found in the book [29].

3.20.9    Matrix Condition Number

Consider the system of equations Ax = b. Matrix A is said to be ill-conditioned if a relatively small change in b (Δb) causes relatively large changes in the solution vector x (Δx). In contrast, matrix A is called a well-conditioned matrix, if a relatively small change in b causes relatively small changes in solution x. Assume A is a square nonsingular matrix and

$A{x}^{\prime }=A\left(x+\Delta x\right)=b+\Delta b,$

(3.144)

where x′ represents the solution error caused by an error Δb in b. Considering Ax = b, it follows that ΑΔx = Δb and hence:

$\Delta x=A^{-1}\Delta b.$

(3.145)

Therefore,

$\Vert \Delta x\Vert \le \Vert A^{-1}\Vert \Vert \Delta b\Vert .$

(3.146)

On the other hand,

$\Vert \Delta b\Vert =\Vert A\Delta x\Vert \le \Vert A\Vert \Vert \Delta x\Vert .$

(3.147)

Therefore,

$\frac{\Vert \Delta b\Vert }{\Vert A\Vert }\le \Vert \Delta x\Vert \le \Vert A^{-1}\Vert \Vert \Delta b\Vert .$

(3.148)

Considering x = A⁻¹ b, and following the same reasoning it is concluded that:

$\frac{\Vert b\Vert }{\Vert A\Vert }\le \Vert x\Vert \le \Vert A^{-1}\Vert \Vert b\Vert .$

(3.149)

From (3.148) and (3.149), it follows that:

$\frac{1}{\Vert A\Vert \Vert A^{-1}\Vert }\frac{\Vert \Delta b\Vert }{\Vert b\Vert }\le \frac{\Vert \Delta x\Vert }{\Vert x\Vert }\le \Vert A\Vert \Vert A^{-1}\Vert \frac{\Vert \Delta b\Vert }{\Vert b\Vert }.$

(3.150)

The number ‖A‖ ‖A⁻¹‖ in3.150 is referred to as the condition number of matrix A and is denoted by cond (A). Therefore,3.150 can be expressed as:

$\frac{1}{\mathrm{cond}\left(A\right)}\left(\frac{\Vert \Delta b\Vert }{\Vert b\Vert }\right)\le \frac{\Vert \Delta x\Vert }{\Vert x\Vert }\le \mathrm{cond}\left(A\right)\left(\frac{\Vert \Delta b\Vert }{\Vert b\Vert }\right).$

(3.151)

This equation relates the relative solution error (‖Δx‖/ ‖x‖) to the relative error in (‖Δb‖/ ‖b‖) If cond (A) is close to 1, then the relative errors in x and b are close. However, if cond (A) is a large number, then the relative errors in x can be significantly larger than the relative errors in b.

3.20.10  Sherman-Morrison-Woodbury Identity

Consider that the system of linear equations Ax = b admits the solution vector x₀. Consider also the slightly changed version of this system of equations under the form: Ãx = b, and whose solution we want to determine under the assumption that à represents a perturbed version of A. The problem that we would like to address is finding a computationally efficient solution for the perturbed system of equations assuming knowledge of x₀ and that à represents a rank-one perturbation of A, i.e.,

$\tilde{A}=A-u{v}^T,$

(3.152)

in which u and v are two arbitrary vectors. Because of3.152, the inverse of à can be expressed in terms of the original matrix A as follows:

${\left(\tilde{A}\right)}^{-1}=A^{-1}+\frac{\left(A^{-1}u\right)\left(v^T{A}^{-1}\right)}{1-v^T{A}^{-1}u}.$

(3.153)

Identity (3.153) is referred to as the Sherman-Morrison identity. Right-multiplying (3.153) with b, the solution of the perturbed system x̃ = (Ã)⁻¹b can be expressed as:

$\tilde{x}={\mathrm{x}}_0+\Delta \mathrm{x}={\mathrm{x}}_0+\frac{\left(A^{-1}u\right)\left(v^T{x}_0\right)}{1-v^T{A}^{-1}u},$

(3.154)

where we took into account A⁻¹b = x₀. Sherman-Morrison formula can be extended to situations when matrix A is subject to higher-order rank perturbations of the form:

$\tilde{A}=A-U{V}^T,$

where U and V are n × m matrices and n > m. In this case, the inverse of the perturbed matrix à is calculated by means of a generalization of the Sherman-Morrison formulation, referred to as the Woodbury identity :

${\left(\tilde{A}\right)}^{-1}=A^{-1}+A^{-1}U{\left(I_m-V^T{A}^{-1}U\right)}^{-1}{V}^T{A}^{-1},$

(3.155)

Equation (3.155) is often referred to as the Sherman-Morrison-Woodbury identity. Right-multiplying (3.155) with vector b, it turns out that the solution of the perturbed system can be expressed in terms of x₀ as follows:

$x^{\prime }=x_0+\Delta x$

(3.156)

$=x_0+A^{-1}U{\left(I_m-V^T{A}^{-1}U\right)}^{-1}{V}^T{x}_0.$

(3.157)

The Sherman-Morrison-Woodbury identities (3.153) and (3.155) play an important role in the development of recursive (iterative or online) estimation and filtering techniques. The RLS algorithm and Kalman filter are two important examples in this regard [10, 11, 30, 31].

3.20.11  Schur Complement

Many practical applications require the calculation of the inverse of a block- partitioned matrix. Assume that the matrix E is block-partitioned as:

$E=\left[\begin{array}{cc}A& B\\ C& D\end{array}\right],$

(3.158)

where submatrix A is invertible. The expression F = D − CA⁻¹ B is called the Schur complement of submatrix A in E and represents an important ingredient in computing the inverse of E in terms of the inverse of A. It turns out that the inverse of the partitioned matrix E in3.158 can be expressed in terms of the inverses of submatrix A and its Schur complement F as follows:

$E^{-1}=\left[\begin{array}{c}{A}^{-1}+A^{-1}B{F}^{-1}C{A}^{-1}-A^{-1}B{F}^{-1}\\ -F^{-1}C{A}^{-1}{F}^{-1}\end{array}\right].$

(3.159)

Furthermore, the determinant of matrix E can be calculated using determinants of submatrix A and its Schur complement:

$\left|E\right|=\left|A\right|\left|F\right|.$

(3.160)

The proof of (3.160) is deferred to Exercise 3.23.32. Additional properties and applications of Schur complement can be found in [7, 32].

3.20.12  Generalized Inverses

Often it is necessary to extend the concept of matrix invertibility to a wider class of rank-deficient matrices by means of concepts such as generalized inverse or pseudoinverse of a matrix. One of the major applications of the concept of generalized inverse is in solving systems of equations of the form: Ax = b, where matrix A is neither square nor nonsingular. Such a system of equations may not admit any solution or may admit an infinite number of solutions.

Basic Definition of Generalized Inverse

The generalized inverse of a matrix is not unique. Any matrix that satisfies the following equation:

$AA͞A=A,$

(3.161)

is referred to as a generalized inverse of matrix A and is denoted by A⁻. In general, the generalized inverse of an m × n matrix is an n × m matrix. Some of the main properties of generalized inverses are enumerated below.

1.  If A is a square and nonsingular matrix, then A⁻ = A⁻¹, i.e., the generalized matrix coincides with the regular inverse.

2.  Transposition: (A^T)⁻ = (A⁻ )^T.

3.  Assume that matrix A is of size m × n, then

(a)  rank (AA⁻) = rank (A) .

(b)  rank (I − A⁻A) = n − rank (A).

4.  Consider m × n matrices A and B and their n × m generalized inverses, A⁻ and A⁻, respectively.

(a)  A (I + A)⁻ = (I + A⁻)⁻ .

(b)  (A⁻ + B⁻)⁻ = A (A + B)⁻B .

(c)  A − A (A + B)⁻ A = B − B (A + B)⁻ B .

(d)  (I + AB)⁻ = I − A (I + BA)⁻ B .

5.  Generalized inverse of block matrices. Consider the block matrix

$E=\left[\begin{array}{cc}A& B\\ C& D\end{array}\right],$

where A, B, C, and D are submatrices of E and A⁻, B⁻, C⁻, and D⁻ stand for their generalized inverses, respectively. The following formula enables calculation of generalized inverse of E:

$E^{ - } = [\begin{array}{c}{A}^{ - } + A^{ - }B{F}^{ - }C{A}^{ - } - A^{ - }B{F}^{ - }\\ - F^{ - }C{A}^{ - }{F}^{ - }\end{array}],$

where F = D −CA⁻B.

An excellent reference dealing with the properties and applications of generalized inverses is [33]. More recently, [7] provides a good list of the major properties exhibited by generalized (weak) inverses.

Generalized Inverses to Solve Consistent Systems of Equations

Assume Ax = b is a consistent under-determined system of equations, i.e., the system of equations admits more than one solution. The generalized inverse A⁻ of matrix A is assumed to satisfy (3.161). Right-multiplying (3.161) with x, it follows that:

$A{A}^{-}Ax=Ax.$

(3.162)

Since Ax = b, (3.162) simplifies further to:

$A\left(A^{-}b\right)=b.$

(3.163)

Therefore, x = A⁻b can be interpreted as a solution of the original system of equations Ax = b. Notice that in general any vector of the form: x = A⁻b + (I − A⁻A) y, where y is any n × 1 vector, is a solution of the original system of equations (and in fact all the solutions are of this type [3]). Indeed, one can check directly by performing the required calculations that

$\begin{array}{c}Ax=A\left(A^{-}b+\left(I-A^{-}A\right)y\right)\\ =A{A}^{-}b+\left(A-A{A}^{-}A\right)y\\ =b-0\\ =b.\end{array}$

The reverse implication can be proved by using the fact that any solution of inhomogeneous system of equations Ax = b can be expressed as the sum between a particular solution (A⁻ b) of the original system Ax = b and the general solution of the homogeneous system of equations Ax = 0, which coincides with the null space of A. It is not difficult to check that I − A⁻A is the projector onto the null space of A [3].

Moore-Penrose Inverse

As mentioned before, the definition of a generalized inverse does not yield a unique generalized inverse, unless it is restricted to satisfy some additional requirements. By imposing several additional constraints to the definition (3.161), a unique generalized inverse can be obtained for any arbitrary matrix A. The resulting unique generalized inverse is referred to as the Moore-Penrose inverse of A and is represented in terms of the notation: A⁺. The additional constraints satisfied by the Moore-Penrose inverse are listed below:

$A^{+}A{A}^{+}=A^{+},$

(3.164)

${\left(A^{+}A\right)}^T=A^{+}A,$

(3.165)

${\left(A{A}^{+}\right)}^T=A{A}^{+}.$

(3.166)

The Moore-Penrose inverse A⁺ exists for any arbitrary matrix A and is unique. There are several methods to calculate the Moore-Penrose inverse of a matrix. One of the most common methods is based on the singular values decomposition of the matrix, explained in Section 3.17. Let the SVD of matrix A be given by A = UΣV^T, where Σ is the same as in (3.122), and matrices U, V are orthogonal. The pseudoinverse of Σ, Σ⁺, is an n × m diagonal matrix with ¹/σ_i, i = 1,… ,r, on its main diagonal, and 0 elsewhere. The Moore-Penrose inverse of A is given by (see e.g., [3, 7, 24]):

$A^{+}=V{\text{Σ}}^{+}{U}^{\hspace{0.17em}}.$

(3.167)

3.21    Matrix Operations

Several useful matrix operations such as Kronecker product, Hadamard product, dot product, direct sum, and matrix differentiation will be introduced in this section.

3.21.1    Kronecker Product

The Kronecker product of m × n matrix A = [a_ij ] and p × q matrix B = [b_ij] is represented in terms of notation ⊗, and it is given by the matrix mp × nq matrix C:

$C=A\otimes B=\left[\begin{array}{cccc}{a}_{11}B& a_{12}B& \dots & a_{1,n}B\\ a_{21}B& a_{22}B& \dots & a_{2n}B\\ ⋮& ⋮& ⋮& ⋮\\ a_{m1}B& a_{m2}B& \dots & a_{mn}B\end{array}\right].$

(3.168)

This Kronecker product is also referred to as direct multiplication.

Suppose that A, B, C, and D are matrices with appropriate sizes. Consider also that a and b are vectors of appropriate sizes, and α and β are scalars. The following properties hold for the Kronecker product (see e.g., [7] for additional properties):

•  (A + B) ⊗ C = A ⊗ C + B ⊗C.

•  A ⊗ (B + C) = A ⊗ B + A ⊗C.

•  (A ⊗ B) ⊗ C = A ⊗ (B ⊗ C).

•  (A ⊗ B) (C ⊗ D) = (AC) ⊗ (BD) .

•  (A ⊗ B)^T = A^T ⊗ B^T .

•  a ⊗ b^T = b^T ⊗ a = ab^T .

•  (A ⊗ B)⁻¹ = A⁻¹ ⊗ B⁻¹ .

•  rank (A ⊗ B) = rank (A) rank (B).

3.21.2    Hadamard Product

The Hadamard product, also called the element-wise or array product, is represented in terms of notation ⊙, and it is defined for two m × n matrices A = [a_k,l] and B = [b_k,l] as follows:

$A\odot B=\left[\begin{array}{cccc}{a}_{1,1}{b}_{1,1}& a_{2,1}{b}_{2,1}& \dots & a_{1,n}{b}_{1,n}\\ a_{2,1}{b}_{2,1}& a_{2,2}{b}_{2,2}& \dots & a_{2,n}{b}_{2,n}\\ ⋮& ⋮& \dots & ⋮\\ a_{m,1}{b}_{m,1}& a_{m,2}{b}_{m,2}& \dots & a_{m,n}{b}_{m,n}\end{array}\right].$

(3.169)

For arbitrary matrices A, B, and C, assumed of appropriate sizes, the Hadamard product exhibits the following properties:

•  A ⊙ B = B ⊙ A

•  (A ⊙B) ⊙ C = A ⊙ (B ⊙C)

•  (A + B) ⊙ C = A ⊙ C + B ⊙ C

•  (A ⊙B)^T = A^T ⊙ B^T

•  C (A ⊙B) = (CA) ⊙ B = A ⊙ (CB)

3.21.3    Dot Product

The dot product, also called the inner-product of two m × n matrices A = [a_i] and B = [b_i] is defined in terms of their column vectors a_i and b_i, respectively, as follows:

$\langle A|B\rangle ={\displaystyle \sum _{i=1}^m{a}_i^T{b}_i}.$

(3.170)

The dot product satisfies the following properties:

•  〈A|B〉 = tr (A^TB)

•  〈A|B〉 = 〈A^T|B^T〉

3.21.4    Direct Sum

The direct sum of k square matrices A₁, A₂, …, A_k with sizes n₁ × n₁, n₂ × n₂, …, n_k × n_k, respectively, is a block diagonal square matrix of size (n₁ + n₂ + … + n_k) × (n₁ + n₂ + … + n_k) defined by

$A_1\oplus A_2\oplus \dots \oplus A_k=\mathrm{diag}\left(A_1,A_2,\dots ,A_k\right)=\left[\begin{array}{cccc}{A}_1& 0& \dots & 0\\ 0& A_2& \dots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \dots & A_k\end{array}\right].$

(3.171)

The following properties of direct sum hold:

•  tr (A₁ ⊕ A₂ ⊕ … A_k) = tr (A₁) + tr (A₂) + … + tr (A_k)

•  |A₁ ⊕ A₂ ⊕ … ⊕ A_k| = |A₁| |A₂|… |A_k|

•  rank (A₁ ⊕ A₂ ⊕ … ⊕ A_k) = rank (A₁) + rank (A₂) + … + rank (A_k)

3.21.5    Differentiation of Matrix and Vector Functions

This subsection focuses on presenting some basic conventions and results regarding the calculation of derivatives for matrix- and vector-valued functions with respect to a scalar, vector, or matrix-valued independent variable.

Differentiation with Respect to a Scalar

When the differentiation variable is a scalar, the derivative has the same structure as the operand and its elements are simply derivatives of the elements of the operand. Assuming that the m × 1 vector x(t) = (x₁(t),…,x_m(t))^T and m × n matrix Y(t) = [y_i,j (t)] are functions of the independent scalar variable t, then their derivatives with respect to t are given by:

$\frac{\partial x\left(t\right)}{\partial t}={\left(\frac{\partial x_1\left(t\right)}{\partial t},\dots ,\frac{\partial x_m\left(t\right)}{\partial t}\right)}^T,$

(3.172)

$\frac{\partial Y\left(t\right)}{\partial t}=\left[\begin{array}{ccc}\frac{\partial y_{1,1}\left(t\right)}{\partial t}& \dots & \frac{\partial y_{1,n}\left(t\right)}{\partial t}\\ ⋮& \ddots & ⋮\\ \frac{\partial y_{m,1}\left(t\right)}{\partial t}& \dots & \frac{\partial y_{m,n}\left(t\right)}{\partial t}\end{array}\right]=\left[\frac{\partial y_{i,j}\left(t\right)}{\partial t}\right].$

(3.173)

Similarly the higher order derivatives of a vector (matrix) with respect to (wrt) a scalar is a vector (matrix) of the same size, and whose entries consist of the higher order derivatives of the vector (matrix) entries.

Differentiation with Respect to a Vector

The derivative of a scalar function x(t) with respect to an n × 1 vector t = (t₁, …,t_n)^T is also referred to as the gradient, and it is defined as the vector:

$\frac{\partial x\left(\mathit{t}\right)}{\partial {\mathrm{t}}^T}=\left(\frac{\partial x\left(\mathit{t}\right)}{\partial t_1},\dots .\frac{\partial x\left(\mathit{t}\right)}{\partial t_n}\right).$

(3.174)

An alternative notation for the gradient of x is:

$\nabla x=\frac{\partial x\left(\mathit{t}\right)}{\partial {\mathrm{t}}^T}.$

(3.175)

The derivative of any operand with respect to a vector yields a vector for each element of the operand. Therefore, the derivative of a vector with respect to a vector is a matrix. Moreover, the derivative of a matrix-valued function with respect to a vector is a three-dimensional array.

Assume the m × 1 vector x(t) = (x₁(t), …,x_m(t))^T and p × q matrix Y(t) = [y_i,_j(t)]. Then the derivatives of x(t) and Y(t) with respect to the n × 1 vector t = (t₁, …,t_n)^T are given by:

$\frac{\partial \text{x}\left(t\right)}{\partial {\mathrm{t}}^T}=\left[\begin{array}{cccc}\frac{\partial x_1\left(t\right)}{\partial t}& \frac{\partial x_1\left(t\right)}{\partial t_2}& \dots & \frac{\partial x_1\left(t\right)}{\partial t_n}\\ \frac{\partial x_2\left(t\right)}{\partial t_1}& \frac{\partial x_2\left(t\right)}{\partial t_2}& \dots & \frac{\partial x_2\left(t\right)}{\partial t_n}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{\partial x_m\left(t\right)}{\partial t_1}& \frac{\partial x_m\left(t\right)}{\partial t_2}& \dots & \frac{\partial x_m\left(t\right)}{\partial t_n}\end{array}\right],$

(3.176)

$\frac{\partial Y}{\partial t}=\left[y_{i,j,k}\right]\text{}\text{},y_{i,k,j}=\frac{\partial y_{i,j}}{\partial t_k},i=1,\cdots ,p,j=1,\dots ,q,k=1,\dots ,n$

(3.177)

The m × n matrix $\frac{\partial \mathrm{x}\left(\mathrm{t}\right)}{\partial {\mathrm{t}}^T}$ is referred to as the Jacobian of x(t) and is usually represented in terms of the notation:

$J_x-\frac{\partial \mathrm{x}}{\partial {\mathrm{t}}^T}.$

(3.178)

Higher order derivatives can be calculated by applying first-order derivatives successively several times; e.g., the second-order derivative of a scalar x(t) with respect to the n × 1 vector t = (t₁, …,t_n)^T is the first-order derivative of the vector $\frac{\partial \mathrm{x}\left(\mathrm{t}\right)}{\partial {\mathrm{t}}^T}={\left(\frac{\partial x\left(t\right)}{\partial t_1},\dots ,\frac{\partial x\left(t\right)}{\partial t_n}\right)}^T$ with respect to the vector t, and it is equal to the matrix:

$\begin{array}{c}\frac{{\partial }^{2}x\left(t\right)}{\partial t\partial t^T}=\frac{\partial }{\partial t}\left(\frac{\partial x\left(t\right)}{\partial t^T}\right)\\ =\frac{\partial }{\partial t}\left(\frac{\partial x\left(t\right)}{\partial t_1},\dots ,\frac{\partial x\left(t\right)}{\partial t_n}\right)\\ =\left(\begin{array}{cccc}\frac{{\partial }^{2}x}{\partial t_1^2}& \frac{{\partial }^{2}x}{\partial t_2{t}_1}& \dots & \frac{{\partial }^{2}x}{\partial t_n{t}_1}\\ \frac{{\partial }^{2}x}{\partial t_1{t}_2}& \frac{{\partial }^{2}x}{\partial t_2^2}& \cdots & \frac{{\partial }^{2}x}{\partial t_n{t}_2}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{{\partial }^{2}x}{\partial t_1{t}_n}& \frac{{\partial }^{2}x}{\partial t_2{t}_n}& \cdots & \frac{{\partial }^{2}x}{\partial t_n^2}\end{array}\right)\\ =\left(\begin{array}{cccc}\frac{{\partial }^{2}x}{\partial t_1^2}& \frac{{\partial }^{2}x}{\partial t_1{t}_2}& \dots & \frac{{\partial }^{2}x}{\partial t_1{t}_n}\\ \frac{{\partial }^{2}x}{\partial t_2{t}_1}& \frac{{\partial }^{2}x}{\partial t_2^2}& \cdots & \frac{{\partial }^{2}x}{\partial t_2{t}_n}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{{\partial }^{2}x}{\partial t_n{t}_1}& \frac{{\partial }^{2}x}{\partial t_n{t}_2}& \cdots & \frac{{\partial }^{2}x}{\partial t_n^2}\end{array}\right).\end{array}$

(3.179)

The matrix in (3.179) is called the Hessian of x(t) and is represented in general in terms of one of these notations:

$\nabla \nabla x={\nabla }^{2}x=\frac{{\partial }^{2}x}{\partial t^2}.$

(3.180)

Derivatives of some commonly used expressions with respect to the n × 1 vector x are shown in Table 3.1. In this table, A stands for an n × n matrix, and x and a are

Table 3.1:  Derivatives of commonly used expressions with respect to vectors.

f (x)	$\frac{\partial f\left(\mathrm{x}\right)}{\partial \mathrm{x}}$	$\frac{\partial f\left(\mathrm{x}\right)}{\partial {\mathrm{x}}^T}$
xT a	a	aT
aT Ax	AT a	aT A
Ax	AT	A
xT x	2x	2xT
xT Ax	Ax + AT x	xT AT + xT A

Table 3.2:  Derivatives of commonly used expressions with respect to matrices.

f(X)	$\frac{\partial f\left(\mathrm{x}\right)}{\partial \mathrm{x}}$
aT Xb	abT
aT XT b	baT
tr(AX)	AT
tr (XXT )	2X
tr (AXB)	AT BT
|X|	|X| (X−1 )T

n × 1 vectors. Generally, the following conventions are adopted $\frac{\partial f\left(\mathrm{x}\right)}{\partial \mathrm{x}}={\left(\frac{\partial f\left(\mathrm{x}\right)}{\partial {\mathrm{x}}^T}\right)}^T$ and $\frac{\partial f\left(\mathrm{x}\right)}{\partial {\mathrm{x}}^T}={\left(\frac{\partial f\left(\mathrm{x}\right)}{\partial \mathrm{x}}\right)}^T$.

Differentiation with Respect to a Matrix

The derivative of each element of an object with respect to a matrix is the matrix of derivatives of that element with respect to the matrix entries. Therefore, the derivatives of a scalar, vector, or a matrix with respect to a matrix are a matrix, three-dimensional array, and four-dimensional array, respectively. Derivatives of some commonly used expressions with respect to a n × n matrix X are depicted in Table 3.2. In this table, A, B, and X are n × n matrices, and a and b are n × 1 vectors. Finally, we would like to mention that reference [7] presents a much more comprehensive description of the results pertaining to the computation of derivatives for vector- and matrix-valued functions.

3.22    References and Further Studies

This chapter presented a short summary of the main concepts and results from linear algebra that are used most frequently in the fields of signal processing, wireless communications, and networking. For more detailed and comprehensive treatment of the basic concepts in linear algebra and matrix theory, the readers are directed to the excellent references [3, 5, 8, 34]. For numerical stable implementations of various matrix factorizations and linear algebra algorithms, [24] represents still one of the state-of-the-art references in this area. The handbook [7] presents an encyclopedic coverage of matrix theory from the viewpoint of a statistician. Another excellent reference that provides an in-depth treatment of basic properties of matrices is [5]. Finally, we end this chapter with the remark that linear algebra represents a very important tool for designing efficient algorithms for signal processing, communications, and networking applications (see e.g., [10, 12, 30, 35]).

Acknowledgment: This work was supported by NSF Grant 0915444.

3.23    Exercises

Exercise 3.23.1. Show that the subset $\mathcal{S}$ ⊂ $\mathcal{V}$, ($\mathcal{S}$ ≠ {0}), where $\mathcal{V}$ is a vector space over field $\mathcal{F}$, is a subspace if and only if

$\forall s_1{s}_2\in \mathcal{S},\forall r_1,r_2\in ℱ:r_1{s}_1+r_2{s}_2\in \mathcal{S}.$

Exercise 3.23.2.Let B = {b₁, b₂,…, b_n} be an ordered basis for vector space $\mathcal{V}$.

•  Show that every inner-product on $\mathcal{V}$ can be computed using the values

$a_{i,j}=\langle b_j|b_i\rangle i=1,\dots ,n,j=1,\dots ,n.$

Hint: Take x, y ∈ $\mathcal{V}$ and write them as linear combinations of b_i’s (i = 1,….n). Form the inner-product 〈x|y 〉 and the coordinate matrices of x and y in the ordered basis B, [x]_B and [y]_B. Show that

$\langle x|y\rangle ={\left[y\right]}_B^{†}A{\left[\mathbf{x}\right]}_B,$

where n × n matrix A = [a_i,j] consists of the inner-products of the vectors in ordered basis B.

•  Show that A is Hermitian positive definite matrix.

Exercise 3.23.3. This problem establishes the Cauchy-Schwarz inequality for the induced norm. Let v be a non-zero vector and define:

$v^{\prime }=w-\frac{\langle w|v\rangle }{\Vert v{\Vert }^2}v.$

Show that 〈v′|v 〉 = 0 and from the fact 0 ≤ ‖v′‖² conclude that

${\left|\langle v|w\rangle \right|}^2\le {\Vert v\Vert }^2{\Vert w\Vert }^2.$

Using this result, prove the triangle inequality for the induced norm.

Exercise 3.23.4. Show that every orthogonal subset B (with non-zero elements) of a vector space $\mathcal{V}$ is linearly independent.

Exercise 3.23.5. Prove that in the Gram-Schmidt orthogonalization process introduced in Theorem 3.1.5, the following relationship holds:

$\langle w_{k+1}|w_i\rangle =0,i=1,\dots ,k.$

Thus, {w₁, w₂,…, w_k+1} is an orthogonal set. Does the set {w₁, w₂,…, w_k+1} represent a basis for span (v₁, v₂,…, v_k+1)7 Justify.

Exercise 3.23.6. Using the fact that for an m × n matrix A, elementary row (column) operations do not affect the column (row) rank, prove that

$\mathrm{row}\mathrm{rank}\left(A\right)=\mathrm{column}\mathrm{rank}\left(A\right).$

Exercise 3.23.7. If A is an m × n matrix over field $\mathcal{F}$, show that the corresponding linear transformation T_A : $\mathcal{F}$ⁿ → $\mathcal{F}$^m is injective if and only if rank (A) = n and is surjective if and only if rank (A) = m.

Exercise 3.23.8. Show that for a projection operation T : $\mathcal{V}$ → $\mathcal{V}$,

$T\left(v\right)=v,\forall v\in ℛ\left(T\right).$

Use this statement to prove Theorem 3.2.3.

Exercise 3.23.9. By computing 〈Pu|(I — P)v 〉 show that a Hermitian idempotent matrix P represents an orthogonal projection. Use this fact to prove Theorem 3.2.4.

Exercise 3.23.10. Let B = {v₁, v₂,…, v_n} be a basis for vector space $\mathcal{V}$.

•  Show that there is a unique linear functional v_i* on $\mathcal{V}$, such that

$v_i^{*}\left(v_j\right)={\delta }_{ij}.$

•  Show that the set of n distinct linear functionals on $\mathcal{V}$ obtained form B (as mentioned above), are linearly independent.

•  From the dimension of $\mathcal{V}$^* what can we conclude about the dual basis of B?

•  Let f be a linear functional on $\mathcal{V}$. Write f as a linear combination of v_i*’s (i = 1, 2,… ,n). Moreover, let v be a vector in $\mathcal{V}$. So we can write it as a linear combination of v_i’s. Write the expression for v_i*(v) and find the unique expression for v as a linear combination of v_i’s (i = 1,…, n).

Exercise 3.23.11. Let T : $\mathcal{V}$ → $\mathcal{W}$ be a linear transformation between two inner-product finite dimensional vector spaces $\mathcal{V}$ and $\mathcal{W}$.

•  Let w ∈ $\mathcal{R}$(T) and n ∈ $\mathcal{N}$ull (T*). By computing 〈w|n 〉 show that

$\mathcal{N}\mathrm{ull}\left(T^{*}\right)\subset ℛ{\left(T\right)}^{\perp }.$

•  Now, let w ∈ $\mathcal{R}$(T)^⊥ . Using the definition of the adjoint of T, show that

$w\in \mathcal{N}\mathrm{ull}\left(T^{*}\right),$

and

$ℛ{\left(T\right)}^{\perp }\subset \mathcal{N}\mathrm{ull}\left(T^{*}\right).$

•  Using the previous results, show that

$ℛ{\left(T\right)}^{\perp }=\mathcal{N}\mathrm{ull}\left(T^{*}\right).$

•  Show that R(T^*)^⊥ = $\mathcal{N}$ull (T) using a similar argument.

Exercise 3.23.12. Using the properties of the four fundamental subspaces of linear transformation T, show that T is surjective if and only if T^* is injective, and T is injective if and only if T^* is surjective.

Exercise 3.23.13. Show the following equalities:

$\begin{array}{c}\mathcal{N}\mathrm{ull}\left(T^{*}T\right)=\mathcal{N}\mathrm{ull}\left(T\right)\\ \mathcal{N}\mathrm{ull}\left(T{T}^{*}\right)=\mathcal{N}\mathrm{ull}\left(T^{*}\right)\\ ℛ\left(T^{*}T\right)=ℛ\left(T^{*}\right)\\ ℛ\left(T{T}^{*}\right)=ℛ\left(T\right).\end{array}$

Hint: First, show that $\mathcal{N}$ull (T) ⊂ $\mathcal{N}$ull (T^*T). Then using the definition of the adjoint, show that if T^*T(v) = 0, then T(v) = 0; and hence, $\mathcal{N}$ull (T*T) ⊂ $\mathcal{N}$ull (T).

Exercise 3.23.14. Show that the two definitions of the operator norm are equivalent, i.e.,

$\begin{array}{c}\Vert T\Vert =\underset{v\in \mathcal{V}-\left\{0\right\}}{\sup }\frac{\Vert T\left(v\right)\Vert }{\Vert v\Vert }\\ =\underset{v\in \mathcal{V},\Vert v\Vert =1}{\sup }\Vert T\left(v\right)\Vert .\end{array}$

Exercise 3.23.15. This problem derives several matrix norms.

•  Using the definition of ‖x‖₁, show that:

$\begin{array}{c}{\Vert A\Vert }_1=\underset{{\Vert x\Vert }_1=1}{\max }{\Vert Ax\Vert }_1\\ =\underset{j}{\max }{\displaystyle \sum _i\left|a_{ij}\right|.}\end{array}$

•  Using the definition of ‖x‖ _∞, show that

$\begin{array}{c}{\Vert A\Vert }_{\infty }=\underset{{\Vert x\Vert }_{\infty }=1}{\max }{\Vert Ax\Vert }_{\infty }\\ =\underset{i}{\max }{\displaystyle \sum _j\left|a_{ij}\right|}.\end{array}$

•  In order to find ‖ A‖₂, use Lagrange’s multiplier technique to minimize

$f\left(x\right)=x^{†}{A}^{†}Ax-\text{λ}\left({\text{x}}^{†}\text{x}-1\right).$

Hint: Take the gradient of f (x) with respect to [x λ] and equate it to zero. Exploit then the eigenvalues and eigenvectors of matrix A^†A.

•  Show that

${\Vert A\Vert }_F^2=\mathrm{tr}\left(A^{†}A\right)={\displaystyle \sum _{i=1}^m{\displaystyle \sum _{j=1}^n{\left|a_{ij}\right|}^2}}.$

Exercise 3.23.16. Let A be an m × n matrix and U be an m × m unitary matrix. Show that

${\Vert UA\Vert }_F={\Vert A\Vert }_F.$

Exercise 3.23.17. Let A and B be matrices of dimension m × n and n × m, respectively. Show that

$\det \left(I_m+AB\right)=\det \left(I_n+BA\right)$

Exercise 3.23.18. Let $\mathcal{S}$ be a subspace of an inner-product vector space $\mathcal{V}$, and let v ∈ $\mathcal{V}$. Follow the steps below to prove Theorem 3.12.1.

•  Suppose s ∈ $\mathcal{S}$ and v – s is orthogonal to all s* ∈ $\mathcal{S}$; i.e.,

$\langle v-s|s^{*}\rangle =0\forall s^{*}\in \mathcal{S}.$

Let s′ ∈ $\mathcal{S}$ and s′ ≠ s. By rewriting the difference v − s′ as

$v-s^{\prime }=\left(v-s\right)+\left(s-s^{\prime }\right),$

show that

${\Vert v-s^{\prime }\Vert }^2\ge {\Vert v-s\Vert }^2.$

•  Conversely, now let ‖v −s′‖², ≤ ‖v−s‖² ∀s′ ∈ S. Show that

$2\Re \left(\langle v-s|s^{*}\rangle \right)+{\Vert s^{*}\Vert }^2\ge 0,\forall s^{*}\in \mathcal{S}.$

Then by a suitable choice for s* show that 〈v − s|s − s′〉 =0 and conclude that v – s is orthogonal to every vector in S.

•  Show that the best approximation is unique.

•  Let ${\displaystyle {\sum }_{k=1}^m\frac{\langle \mathrm{v}|s_k\rangle }{\Vert {\mathrm{s}}_k\Vert }{\mathrm{S}}_k}$ Show that v–s is orthogonal to s_j , j = 1,…, m, and it is orthogonal to every vector in S. Therefore, s is the best approximation of v by vectors in S.

Exercise 3.23.19. Let $\mathcal{S}$ be a finite-dimensional subspace of inner-product vector space $\mathcal{V}$. Suppose P is an orthogonal projection of $\mathcal{V}$ onto $\mathcal{S}$.

•  Prove that the mapping defined by matrix I − P which maps any vector v ∈ $\mathcal{V}$ onto v − Pv is actually the orthogonal projection of $\mathcal{V}$ onto $\mathcal{S}$^⊥.

•  Show that P is an idempotent linear mapping from $\mathcal{V}$ to $\mathcal{S}$.

•  Show that

$P{s}^{\prime }=0\iff s^{\prime }\in {\mathcal{S}}^{\perp }.$

•  Show that

$\mathcal{V}=\mathcal{S}\oplus {\mathcal{S}}^{\perp }.$

Exercise 3.23.20. This problem pertains to the proof of Theorem 3.13.1.

•  Using the best approximation theorem and the four fundamental subspaces related to T, show that the minimum error (T(v) − w) should be in the nullspace of T^*.

•  Conclude that

$T^{*}T\left(v\right)=T^{*}\left(w\right).$

Exercise 3.23.21. Show that if an n × n matrix A has distinct eigenvalues, the corresponding eigenvectors should be linearly independent.

Exercise 3.23.22. Let v_i and v_j be two eigenvectors of an n × n Hermitian matrix A, corresponding to different eigenvalues λ_i and λ_j, respectively. Compute ${\mathrm{v}}_i^{†}{\mathrm{v}}_j$ and show that the eigenvectors are orthogonal. Moreover, by computing ${\mathrm{v}}_i^{†}\text{A}{\mathrm{v}}_i$, show that A’s eigenvalues are real. Use these results to prove the claims of Theorem 3.15.2.

Exercise 3.23.23. This problem is related to diagonalizing a matrix (Theorem 3.15.3). Suppose v₁, v₂,…, v_n are n linearly independent eigenvectors of an n × n matrix A, corresponding to eigenvalues λ₁, λ₂,… ,λ_n, respectively.

•  Show that

$A\left[v_1,v_2,\dots ,v_n\right]=\left[v_1,v_2,\dots ,v_n\right]\left[\begin{array}{ccc}{\text{λ}}_1& & \\ & \ddots & \\ & & {\text{λ}}_n\end{array}\right].$

Define S = [v₁, v₂,…, v_n] and Λ = diag (λ₁,…, λ_n), where diag (·) is a diagonal matrix. Note that S is invertible. Conclude that A is diagonalizable.

•  Conversely, let S be an invertible matrix such that

$S^{-1}AS=\text{Λ},$

where Λ is diagonal. Show that the i^th column of S is an eigenvector of A, corresponding to the i^th diagonal entry of Λ.

Exercise 3.23.24. Using the SVD of matrix A, show that

${\Vert A\Vert }_F={\left({\sigma }_1^2+{\sigma }_2^2+\cdots +{\sigma }_n^2\right)}^{1/2},$

where n is the rank of A and σ_i (i = 1,…, n) are the singular values of A.

Exercise 3.23.25. Show that the multiplication of block matrices $\mathrm{A}=\left[\begin{array}{c}{\mathrm{A}}_{11}{\mathrm{A}}_{12}\\ {\mathrm{A}}_{21}{\mathrm{A}}_{22}\end{array}\right]$ and $\mathrm{B}=\left[\begin{array}{c}{\mathrm{B}}_{11}{\mathrm{B}}_{12}\\ {\mathrm{B}}_{21}{\mathrm{B}}_{22}\end{array}\right]$ can be expressed as:

$AB=\left[\begin{array}{c}{A}_{11}{B}_{11}+A_{12}{B}_{21}{A}_{1,1}{B}_{12}+A_{12}{B}_{22}\\ A_{21}{B}_{11}+A_{22}{B}_{21}{A}_{21}{B}_{12}+A_{22}{B}_{22}\end{array}\right].$

Exercise 3.23.26. Let the permutation matrix ∏_m be defined as follows:

${\Pi }_m=circ\left(0,1,0,\dots ,0\right)=\left[e_m,e_1,e_2,\dots ,e_{m-1}\right],$

with

$e_i=\begin{array}{c}\begin{array}{lllllll}1\hfill & \dots \hfill & i-1\hfill & i\hfill & i+1\hfill & \dots \hfill & m^T\hfill \end{array}\\ \left(\begin{array}{lllllllll}0\hfill & \dots \hfill & 0\hfill & \hfill & 1\hfill & 0\hfill & \dots \hfill & \hfill & 0\hfill \end{array}\right).\end{array}$

Prove that the square matrix A is circulant if and only if $\mathrm{A}={\displaystyle {\prod }_m\mathrm{A}{\displaystyle \prod {}_m^T}}$.

Exercise 3.23.27. Using the result proved in Exercise 3.23.26, justify the following properties.

•  If A and B are circulant matrices, then AB is a circulant matrix.

•  If A is circulant, then A⁻¹ is a circulant matrix.

Exercise 3.23.28. Show that:

•  The eigenvalues of a circulant matrix (c_o, c₁,…, c_n−1) are

${\text{λ}}_k={\displaystyle \sum _{i=0}^{n-1}{c}_i{e}^{-j2\pi ik/n}.}$

•  The corresponding eigenvectors are

$x_k=\frac{1}{\sqrt{n}}{\left[\begin{array}{lllll}1\hfill & e^{-j2\pi k/n}\hfill & e^{-j2\pi \left(2k\right)/n}\hfill & \dots \hfill & e^{-j2\pi \left(n-1\right)k/n}\hfill \end{array}\right]}^T.$

Exercise 3.23.29. Using the equation for determinant of a Vandermonde matrix, what conditions must the scalars a₁, a₂, …, a_n satisfy in order for Vandermonde matrix A to be invertible?

$A=\left[\begin{array}{lllll}1\hfill & a_1\hfill & a_1^2\hfill & \dots \hfill & a_1^{m-1}\hfill \\ 1\hfill & a_2\hfill & a_2^2\hfill & \dots \hfill & a_2^{m-1}\hfill \\ ⋮\hfill & ⋮\hfill & ⋮\hfill & \ddots \hfill & ⋮\hfill \\ 1\hfill & a_m\hfill & a_m^2\hfill & \cdots \hfill & a_m^{m-1}\hfill \end{array}\right].$

Exercise 3.23.30. Consider the square matrix A. Prove that:

1.  If A is positive definite, then all its eigenvalues are positive.

2.  If all eigenvalues of A are positive, A is positive definite.

Exercise 3.23.31. Prove that the following factorization is valid for the block-partitioned matrix M:

$M=\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]=\left[\begin{array}{cc}A& 0\\ C& E\end{array}\right]\left[\begin{array}{cc}I{A}^{-1}& B\\ 0& I\end{array}\right],$

where E is the Schur complement of submatrix A in matrix M.

Exercise 3.23.32. Consider the block matrix

$M=\left[\begin{array}{cc}A& B\\ C& D\end{array}\right].$

Prove that the determinant of matrix M is equal to the product of determinants of A and its Schur complement.

Exercise 3.23.33. Show that the generalized inverse of the block matrix

$M=\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]$

is given by:

$M^{ - 1} = [\begin{array}{c}{A}^{ - } + A^{ - }B{E}^{ - }C{A}^{ - } - A^{ - }B{E}^{ - }\\ - E^{ - }C{A}^{ - }{E}^{- }\end{array}],$

where E = D − CA⁻B.

Exercise 3.23.34. Prove the following properties of the Kronecker product. Matrices A, B, C and D are assumed of appropriate sizes.

1.  (A + B) ⊗ C = A ⊗C + B ⊗ C.

2.  (A ⊗ B) ⊗ C = A ⊗ (B ⊗ C).

3.  (αA) ⊗ (βB) = αβ (A ⊗ B).

4.  (A ⊗ B) (C ⊗ D) = (AC) ⊗ (BD).

Exercise 3.23.35. Prove the vector and matrix derivative results presented in Tables 3.1 and 3.2, respectively.

References

[1]  J. E. Gentle, Matrix Algebra: Theory, Computations, and Applications in Statistics. NY: Springer, 2010.

[2]  S. Leon, Linear Algebra with Applications. 9th ed., NY: Prentice Hall, 2009.

[3]  A. J. Laub, Matrix Analysis for Scientists and Engineers, Philadephia: SIAM, 2004.

[4]  P. Lax, Linear Algebra and Its Applications. 2nd ed., NY: Wiley Interscience, 2007.

[5]  C. Meyer, Matrix Analysis and Applied Linear Algebra Book. Philadephia: SIAM, 2001.

[6]  S. Roman, Advanced Linear Algebra. 3rd ed., NY: Springer, 2010.

[7]  G. A. F. Seber, A Matrix Handbook for Statisticians. NY: Wiley, 2008.

[8]  G. Strang, Linear Algebra and Its Applications. Cengage Learning, Florence, KY: Brooks Cole, 2005.

[9]  R. A. Horn and C. R. Johnson, Matrix Analysis. Cambridge: Cambridge University Press, 1985.

[10]  S. Kay, Fundamentals of Statistical Signal Processing, vol. I: Estimation Theory, vol. II: Detection Theory. 1st ed., NY: Prentice Hall, 1993.

[11]  A. H. Sayed, Adaptive Filters. 1st ed., NY: Wiley-IEEE Press, 2008.

[12]  P. Stoica and R. L. Moses, Spectral Analysis of Signals. NY: Prentice Hall, 2005. 91

[13]  J. Dauxois and G. M. Nkiet, “Canonical analysis of two Euclidean subspaces and its applications,” Linear Algebra Appl., vol. 264, no. 10, pp. 355–388, October 1997.

[14]  R. Gittins, Canonical Analysis: A Review with Applications in Ecology, Biomathematic, Berlin: Springer-Verlag, 1985.

[15]  T. Kailath, “A view of three decades of linear filtering theory,” IEEE Transactions on Information Theory, vol. 20, no. 2, pp. 146–181, February 1974.

[16]  I. M. Gelfand and A. M. Yaglom, “Calculation of the amount of information about a random function contained in another such function,” American Mathematical Society Translations, series vol. 12, pp. 199–246, 1959.

[17]  H. Akaike, “Stochastic theory of minimal realization,” IEEE Transactions on Automatic Control, pp. 667–674, 1974.

[18]  P. E. Caines, Linear Stochastic Systems. NY: Wiley, 1988.

[19]  P. V. Oversche and B. de Moor, Subspace Identification for Linear Systems: Theory, Implementation and Applications. Boston: Kluwer Academics Publishers, 1996.

[20]  T. Kim, O. Arandjelovic, and R. Cipolla, “Boosted manifold principal angles for image set-based recognition,” Pattern Recognition, vol. 40, issue 9, pp. 2475–2484, September 2007.

[21]  L. Wolf and A. Shashua, “Learning over Sets using Kernel Principal Angles,” Journal of Machine Learning Research, vol. 4, pp. 913–931, 2003.

[22]  R. T. Behrens and L. Scharf, “Signal Processing Applications of Oblique Projection Operators,” IEEE Transactions on Signal Processing, vol. 42, no. 6, pp. 1413–1414, June 1994.

[23]  I. E. Telatar, “Capacity of multi-antenna Gaussian channels,” Eur. Trans. Telecommun., vol. 10, no. 6, pp. 585–595, November 1999.

[24]  G. Golub and C. F. van Loan, Matrix Computations. 3rd. ed., Baltimore: John Hopkins University Press, 1996.

[25]  I. Jolliffe, Principal Component Analysis. Berlin: Springer, 2002.

[26]  S. K. Mitra, Digital Signal Processing. NY: McGraw-Hill, 2005.

[27]  R. M. Gray, Toeplitz and Circulant Matrices: A Review. Boston-Delft: Now Publishers Inc., 2005.

[28]  M. Verhaegen, “Identification of the Deterministic Part of MIMO State Space Models given in Innovations Form from Input-Output Data,” Automatica, vol. 30, no. 1, pp. 61–74, January 1994.92

[29]  R. Bhatia, Positive Definite Matrices. Princeton: Princeton University Press, 2006.

[30]  S. Haykin, Adaptive Filter Theory. NY: Prentice Hall, 2002.

[31]  T. Soderstrom and P. Stoica, System Identification. NY: Prentice Hall, 1994.

[32]  F. Zhang, The Schur Complement and Its Applications. Berlin: Springer, 2010.

[33]  C. R. Rao and S. K. Mitra, Generalized Inverse of Matrices and Its Applications. NY: Wiley, 1972.

[34]  T. K. Moon and W. C. Stirling, Mathematical Methods and Algorithms for Signal Processing. Upper Saddle River, NJ: Prentice-Hall, 2000.

[35]  S. B. Wicker, Error Control Systems for Digital Communication and Storage. Upper Saddle River, NJ: Prentice-Hall, 1995.