Question

Consider the saddle point matrix $$ K=\left(\begin{array}{cc} H & A^{T} \\ A & 0 \end{array}\right) $$ where the matrix \(H\) is symmetric positive semidefinite and the matrix \(A\) has full row rank. (a) Show that \(K\) is nonsingular if \(\mathbf{y}^{T} H \mathbf{y} \neq 0\) for all \(\mathbf{y} \in \operatorname{null}(A), \mathbf{y} \neq \mathbf{0}\). (b) Show by example that \(K\) is symmetric but indefinite, i.e., it has both positive and negative eigenvalues.

Short answer

Answer: Yes, the saddle-point matrix K is nonsingular if the given condition is satisfied, and it is symmetric and indefinite.

Step-by-step solution

Proving Nonsingularity

To prove that K is nonsingular if the given condition is satisfied, let's assume the contrary, i.e. K is singular. This means that there exists a nonzero vector \(\mathbf{x}\) such that \(K\mathbf{x}=\mathbf{0}\). For \(\mathbf{x}=\begin{pmatrix}\mathbf{y} \\ \mathbf{\xi} \end{pmatrix}\), it can be written as: $$ \begin{pmatrix} H & A^T \\ A & 0 \end{pmatrix} \begin{pmatrix} \mathbf{y} \\ \mathbf{\xi} \end{pmatrix} = \begin{pmatrix} \mathbf{0} \\ \mathbf{0} \end{pmatrix} $$ Let's split the above into two systems: System 1: \(H\mathbf{y} + A^T\mathbf{\xi} = \mathbf{0}\) System 2: \(A\mathbf{y} = \mathbf{0}\) Notice that System 2 states that \(\mathbf{y} \in \operatorname{null}(A)\). Since H is positive semidefinite, we have: \(\mathbf{y}^TH\mathbf{y} \ge 0\). Now, using System 1 and the property of \(\xi\) being nonzero, we can write the inner product of System 1 with \(\mathbf{y}\): \(\mathbf{y}^T(H\mathbf{y} + A^T\mathbf{\xi}) = \mathbf{y}^TH\mathbf{y} + \mathbf{y}^TA^T\mathbf{\xi} = \mathbf{y}^TH\mathbf{y} + (\mathbf{\xi}^TA\mathbf{y})= \mathbf{y}^TH\mathbf{y}=0\); Now, we have reached a contradiction since it's given that \(\mathbf{y}^TH\mathbf{y}\neq 0\) for all y in the null space of A and \(\mathbf{y} \neq \mathbf{0}\). Therefore, our initial assumption that K is singular is false, implying that K is nonsingular.

Proving Symmetry of K

To prove that K is symmetric, we need to show that \(K^T = K\). We know that \(H^T=H\), as H is symmetric, and A is any arbitrary matrix; thus: $$ K^T = \begin{pmatrix} H & A^T \\ A & 0 \end{pmatrix}^T = \begin{pmatrix} H^T & A^T \\ A^T & 0^T \end{pmatrix} = \begin{pmatrix} H & A^T \\ A & 0 \end{pmatrix} = K $$ This confirms that K is symmetric.

Example to show K has both positive and negative eigenvalues

Let's consider the following example for matrix H and A: $$ H = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, A = \begin{pmatrix} 1 & 0 \end{pmatrix} $$ Now, the saddle point matrix K becomes: $$ K = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix} $$ Let's calculate the eigenvalues of K. We need to solve the following for λ: $$ \det(K-\lambda I) = \begin{vmatrix} 1-\lambda & 0 & 1 \\ 0 & 1-\lambda & 0 \\ 1 & 0 & -\lambda \end{vmatrix} =(1-\lambda)^2(-\lambda)-(1-\lambda)=\lambda^3 - 2\lambda^2 + \lambda = \lambda(\lambda-1)^2 $$ The eigenvalues are \(\lambda_1 = 0\), \(\lambda_2 = 1\), and \(\lambda_3 = 1\). Since we have both positive and negative eigenvalues (1 and 0), this proves that K is indefinite.

Key concepts

Understanding Nonsingular Matrices

In linear algebra, a matrix is considered nonsingular or invertible if and only if it does not map different vectors in its domain to the same vector in its codomain, and it has an inverse matrix. In other words, a nonsingular matrix is a matrix that does not compress the space in such a way that would make different inputs lead to a single output.

For a square matrix A, being nonsingular is equivalent to the statement that if Ax = 0 has only the trivial solution x = 0, then for any vector b, the equation Ax = b has a unique solution. Therefore, the system is consistent and has a unique solution. Additionally, for a matrix to be nonsingular, its determinant must be nonzero.

As seen in the saddle point matrix exercise, establishing the nonsingularity of K depends on the condition that y^THy ≠ 0 for all nonzero y within the null space of A. This fact aligns with the nonsingularity concept, as it confirms the absence of nontrivial solutions to Kx = 0, ensuring a unique solution exists to equations involving K.

Symmetric Positive Semidefinite Matrices

A matrix H is said to be symmetric positive semidefinite (PSD) if it's symmetric (H = H^T), meaning it's equal to its own transpose, and for any vector x, x^THx ≥ 0. This definition encompasses the concept of non-negativity of quadratic forms, which is a practical way of understanding the properties of constrained optimization situations and stability in physical and economic systems.

Symmetric positive semidefinite matrices have several important properties, including all eigenvalues being non-negative. This is significant because the sign of the eigenvalues determines certain characteristics of optimization problems, such as whether a function has a minimum, maximum, or saddle point at a given point.

In the context of the saddle point matrix K, the matrix H being positive semidefinite assures that the quadratic form defined by H will not produce negative values, which is pivotal in proving the nonsingularity of K by contradiction in the provided solution to the exercise.

The Role of Eigenvalues in Matrix Analysis

Eigenvalues are fundamental to understanding the behavior of matrices. An eigenvalue \( \lambda \) is a special scalar associated with a linear transformation represented by a matrix A, such that there exists a nonzero vector v (the eigenvector) for which \( Av = \lambda v \). Consequently, the eigenvalue indicates the factor by which the eigenvector is scaled during the transformation.

Eigenvalues reveal much about the matrix, including whether it is invertible (all eigenvalues are nonzero), whether it is a positive definite matrix (all eigenvalues are positive), or whether it has a tendency to amplify or dampen the applied vector (based on whether the absolute value of eigenvalues is more or less than one).

In the saddle point matrix example, examining the eigenvalues of the matrix K illustrated its indefinite nature as it had both positive and zero eigenvalues. While a positive eigenvalue generally implies a stretching in the direction of the corresponding eigenvector, a zero eigenvalue implies that K is not only symmetric but also indicative of the existence of a saddle point, thus proving that K is indeed indefinite.