Question

This exercise is for lovers of complex arithmetic. Denote by \(\mathbf{x}^{H}\) the conjugate transpose of a given complex-valued vector \(\mathbf{x}\), and likewise for a matrix. The \(\ell_{2}\) -norm is naturally extended to complex- valued vectors by $$ \|\mathbf{x}\|_{2}^{2}=\mathbf{x}^{H} \mathbf{x}=\sum_{i=1}^{n}\left|x_{i}\right|^{2}, $$ which in particular is real, possibly unlike \(\mathbf{x}^{T} \mathbf{x}\). A complex-valued \(n \times n\) matrix \(A\) is called Hermitian if \(A^{H}=A\). Further, \(A\) is positive definite if $$ \mathbf{x}^{H} A \mathbf{x}>0 $$ for all complex-valued vectors \(\mathbf{x} \neq \mathbf{0}\). (a) Show that the \(1 \times 1\) matrix \(A=t\) is symmetric but not Hermitian, whereas \(B=\left(\begin{array}{cc}2 & t \\ -1 & 2\end{array}\right)\) is Hermitian positive definite but not symmetric. Find the eigenvalues of \(A\) and of \(B\). [In general, all eigenvalues of a Hermitian positive definite matrix are real and positive.] (b) Show that an \(n \times n\) Hermitian positive definite matrix \(A\) can be decomposed as \(A=\) \(L D L^{H}\), where \(D\) is a diagonal matrix with positive entries and \(L\) is a complex-valued unit lower triangular matrix. (c) Extend the Cholesky decomposition algorithm to Hermitian positive definite matrices. Justify.

Short answer

Q2: What is the primary difference between a symmetric matrix and a Hermitian matrix? Q3: State True or False: A Hermitian positive definite matrix A always has real and positive eigenvalues. Q4: What are the two components of the decomposition A = LDL^H, where A is an n x n Hermitian positive definite matrix? Q5: Summarize the extended Cholesky decomposition algorithm for Hermitian positive definite matrices.

Step-by-step solution

Prove the given properties of matrices A and B

To check if a given matrix is symmetric or Hermitian, we need to compare the matrix with its transpose and its conjugate transpose, respectively. Given matrix A = t, we can see that its transpose is A^T = t and its conjugate transpose is A^H = conj(t). Since t = A^T, A is symmetric. However, A is not Hermitian as A ≠ A^H (unless t is a real number). Now for matrix B, we need to find its transpose B^T and its conjugate transpose B^H: B^T = \(\begin{pmatrix}2 & -1 \\ t & 2\end{pmatrix}\) B^H = \(\begin{pmatrix}2 & \bar{t} \\ -1 & 2\end{pmatrix}\) Since B ≠ B^T, B is not symmetric. However, B = B^H, so B is Hermitian. To show that B is positive definite, let x be any complex-valued non-zero vector: $$x = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}$$ Then, $$x^H B x = \begin{pmatrix} \bar{x_1} & \bar{x_2} \end{pmatrix} \begin{pmatrix}2 & t \\ -1 & 2\end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}$$ $$=\begin{pmatrix} (2\bar{x_1}-\bar{x_2}) & (t\bar{x_1}+2\bar{x_2}) \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}$$ $$= (2x_1\bar{x_1}-x_1\bar{x_2}-x_2\bar{x_1}+2x_2\bar{x_2}) > 0$$ Since this expression is greater than 0 for any non-zero complex-valued vector x, B is positive definite.

Find eigenvalues of matrices A and B

To find the eigenvalues of a matrix, we need to solve the characteristic equation det(A - λI) = 0 and det(B - λI) = 0, respectively. For A = t, the characteristic equation is: $$det(A - \lambda I) = det\begin{pmatrix}t-\lambda\end{pmatrix} = (t - \lambda) = 0$$ Hence, the eigenvalue of A is λ = t. For B, the characteristic equation is: $$det(B - \lambda I) = det\begin{pmatrix}2-\lambda & t \\ -1 & 2-\lambda\end{pmatrix} = (2 - \lambda)^2 - (-t) = 0$$ Solving this quadratic equation, we get: $$\lambda^2 - 4\lambda + 4 + t = (\lambda-2)^2 + t = 0$$ Since the matrix B is Hermitian positive definite, the eigenvalues are real and positive. Therefore, the eigenvalues of B are: $$\lambda_1 = 2 + \sqrt{t}$$ $$\lambda_2 = 2 - \sqrt{t}$$

Prove Hermitian positive definite matrix decomposition

We need to show that any n x n Hermitian positive definite matrix A can be decomposed as A = LDL^H, where D is a diagonal matrix with positive entries, and L is a complex-valued unit lower triangular matrix. The proof can be done via induction on the size of n. - Base case: n = 1, the matrix A is just a scalar, say a. Then, L = [1], D = [a], and LDL^H = [a], which is equal to A. - Inductive step: Suppose the decomposition is true for all Hermitian positive definite matrices of size (n-1) x (n-1). If A is an n x n Hermitian positive definite matrix, then partition A as follows: $$A = \begin{pmatrix} B & w \\ w^H & a \end{pmatrix}$$ where B is an (n-1) x (n-1) Hermitian positive-definite matrix, w is an (n-1) x 1 vector, and a is a scalar. By induction hypothesis, we have: $$B = MDM^H$$ where M is a complex-valued unit lower triangular matrix and D is a diagonal matrix with positive entries. Now we can define L and D for the n x n matrix A as follows: $$L = \begin{pmatrix} M & 0 \\ \frac{1}{d_n}(DM^H)^{-1}w & 1 \end{pmatrix}$$ $$D = \begin{pmatrix} D & 0 \\ 0 & d_n \end{pmatrix}$$ We can verify that the decomposition A = LDL^H holds. The product LDL^H becomes: $$LDL^H = \begin{pmatrix} M & 0 \\ \frac{1}{d_n}(DM^H)^{-1}w & 1 \end{pmatrix} \begin{pmatrix} D & 0 \\ 0 & d_n \end{pmatrix} \begin{pmatrix} M^H & w^H(DM^H)^{-1}d_n \\ 0 & 1 \end{pmatrix}$$ $$= \begin{pmatrix} B & w \\ w^H & a \end{pmatrix} = A$$ Thus, the decomposition of A holds true for a Hermitian positive definite matrix of size n x n.

Extend Cholesky decomposition algorithm

To extend the Cholesky decomposition algorithm for Hermitian positive definite matrices, we need to replace transpose (T) operations with conjugate transpose (H) operations in the Cholesky algorithm. The algorithm would then look like this: 1. Initialize an empty matrix L of the same size as matrix A. 2. For each row i from 1 to n, do the following: a) For each column j from 1 to i, calculate: - If j == i, $$L_{ij} = \sqrt{A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{ik}^H}$$ - If j < i, $$L_{ij} = \frac{1}{L_{jj}^H}(A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{jk}^H})$$ 3. The matrix L is the desired lower complex-valued unit triangular matrix such that A = LL^H. Justification: The above algorithm is a direct extension of the Cholesky decomposition algorithm for real-valued positive definite matrices. By replacing transpose operations with conjugate transpose operations, we maintain the Hermitian and positive-definite properties of the input matrix A. The result will still be a unique lower unit triangular matrix L such that A = LL^H for a Hermitian positive definite matrix A.

Key concepts

Complex Arithmetic

Complex arithmetic deals with numbers that have both real and imaginary parts. These numbers are typically in the form of \( a + bi \), where \( a \) is the real part, and \( bi \) is the imaginary part. The imaginary unit \( i \) has the property \( i^2 = -1 \). Complex arithmetic is crucial in various mathematical fields, including linear algebra, where matrices and vectors often have complex entries.

In the context of matrices, the complex conjugate of a matrix involves taking the complex conjugate of each element. For a vector \( \mathbf{x} \), its conjugate transpose (also known as Hermitian transpose and denoted \( \mathbf{x}^H \)) is found by taking its transpose and then replacing each entry by its complex conjugate. This operation maintains important properties of matrices in complex arithmetic, such as the determinant and eigenvalues.

The \( \ell_2 \)-norm is an extension of the Euclidean norm to complex vectors, calculated using \( \|\mathbf{x}\|_2^2 = \mathbf{x}^H \mathbf{x} = \sum_{i=1}^{n}|x_i|^2 \). This norm provides a measure of the vector's size and is always a real number, even when \( \mathbf{x} \) has complex-valued elements.

Positive Definite

A Hermitian matrix \( A \) is called positive definite if it satisfies the condition \( \mathbf{x}^H A \mathbf{x} > 0 \) for all non-zero complex-valued vectors \( \mathbf{x} \). This mathematical property ensures that a matrix behaves similarly to positive real numbers and is essential in optimization problems and stability analysis.

Key characteristics of positive definite matrices include:

• Eigenvalues: All eigenvalues of a positive definite matrix are real and positive. This not only indicates the sense of direction in which the transformation represented by the matrix stretches, but it also guarantees invertibility.
• Cholesky Decomposition: The positive definiteness is a requirement for this decomposition method, which simplifies many matrix computations.

In applications, positive definite matrices often represent energy quantities or other physical properties that must be non-negative, ensuring the stability of systems modeled by these matrices.

Cholesky Decomposition

The Cholesky decomposition is a numerical method used to factor a Hermitian positive definite matrix \( A \) into the product \( LL^H \), where \( L \) is a lower triangular matrix with complex entries and \( L^H \) is its conjugate transpose. This decomposition is useful in solving systems of linear equations, computing determinants, and matrix inversions.

The Cholesky decomposition simplifies computations by breaking down complex matrix operations into easier calculations involving the triangular matrix \( L \). Here's a brief overview of the process:

• Start by initializing an empty matrix \( L \) of the same size as \( A \).
• Compute the entries of \( L \) row by row using the rules:
  • If \( i = j \), compute \( L_{ij} = \sqrt{A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{ik}^H} \).
  • If \( i > j \), compute \( L_{ij} = \frac{1}{L_{jj}^H}(A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{jk}^H) \).

This method leverages the symmetry of Hermitian matrices and is highly efficient for large matrices, especially in numerical simulations.

Eigenvalues

Eigenvalues are scalar values that, when a matrix is multiplied by a vector, produce a resultant vector parallel to the original vector. Finding eigenvalues of a matrix involves solving the characteristic equation \( \det(A - \lambda I) = 0 \), where \( A \) is the matrix, \( I \) is the identity matrix, and \( \lambda \) represents the eigenvalues.

For Hermitian matrices, a significant property is that all eigenvalues are real. This is vital for the structural stability of a matrix. In the context of positive definite matrices, eigenvalues are not only real but also positive, indicating that the matrix is invertible and related transformations will not result in reversal or collapse to a lower dimension.

Understanding eigenvalues is essential in fields like quantum mechanics, vibration analysis, and principal component analysis, where they indicate resonant frequencies, directions of data variance, and stability regions of systems.