Linear Algebra Foundation based Homework Problems - Positive defnite matrices

Positive Definite Matrices

A matrix $A \in \mathbb{R}^{n \times n}$ is positive semi-definite (PSD), denoted $A \succeq 0$, if $A = A^T$ and $x^T A x \geq 0$ for all $x \in \mathbb{R}^n$. A matrix $A$ is positive definite, denoted $A \succ 0$, if $A = A^T$ and $x^T A x > 0$ for all $x \neq 0$, that is, all non-zero vectors $x$. The simplest example of a positive definite matrix is the identity $I$ (the diagonal matrix with 1s on the diagonal and 0s elsewhere), which satisfies $x^T I x = \|x\|^2 = \sum\_{i=1}^{n} x_i^2$.

(a) Let $z \in \mathbb{R}^n$ be an n-vector. Show that $A = zz^T$ is positive semidefinite.

(b) Let $z \in \mathbb{R}^n$ be a non-zero n-vector. Let $A = zz^T$. What is the null-space of $A$? What is the rank of $A$?

(c) Let $A \in \mathbb{R}^{n \times n}$ be positive semidefinite and $B \in \mathbb{R}^{m \times n}$ be arbitrary, where $m, n \in \mathbb{N}$. Is $BAB^T$ PSD? If so, prove it. If not, give a counterexample with explicit $A, B$.

Solutions

Problem 2(a)

To solve problem (a), we need to show that the matrix $A = zz^T$ is positive semidefinite (PSD). A matrix $A$ is positive semidefinite if, for any vector $x \in \mathbb{R}^n$, the following condition is satisfied:

$x^T A x \geq 0$

Here are the steps to show that $A = zz^T$ is PSD:

1. Apply the definition: For any vector $x$, we need to consider $x^T A x$ and show that this is always greater than or equal to 0.

2. Substitute $A$ with $zz^T$: We have $x^T A x = x^T (zz^T) x$.

3. Use matrix multiplication: Remember that matrix multiplication is associative, so we can rearrange the multiplication as $(x^T z)(z^T x)$.

4. Recognize the dot product: The term $(x^T z)$ is a dot product of $x$ and $z$, which gives a scalar. Let's denote it as $c$, so $c = x^T z$ and $c$ is a real number since it's a scalar.

5. Express $c$ as a scalar multiplication: We now have $c(z^T x)$, which is the same as $c^2$ because $z^T x$ will also give the same dot product as $x^T z$.

6. Conclude the proof: We know that $c^2$ is always non-negative for any real number $c$, and hence $x^T A x = c^2 \geq 0$.

So, we have shown that for any vector $x$, $x^T A x$ is always non-negative, hence $A = zz^T$ is positive semidefinite.

Problem 2(b)

Problem (b) asks for the null-space and the rank of the matrix $A = zz^T$, where $z$ is a non-zero $n$-vector.

Here's how to solve it:

1. Null-space: The null-space (or kernel) of $A$ consists of all vectors $x$ such that $Ax = 0$. So we need to solve $zz^T x = 0$ for $x$.

   Since $z$ is non-zero, $zz^T$ is a rank-1 matrix (because each row is a multiple of $z$), and the only vector that gets mapped to the zero vector by $zz^T$ is a vector orthogonal to $z$. Therefore, the null-space is the set of all vectors that are orthogonal to $z$.

2. Rank: The rank of a matrix is the dimension of the column space (the space spanned by its columns). Since $A = zz^T$ has each column as a multiple of $z$, and $z$ is non-zero, the column space is the line through $z$ (and the origin). Therefore, the rank of $A$ is 1, because there is only one linearly independent column in $A$.

So the null-space of $A$ is the $(n-1)$-dimensional subspace of $\mathbb{R}^n$ orthogonal to $z$, and the rank of $A$ is 1.

Problem 2(c)

To solve problem (c), we are asked to determine if the matrix $BAB^T$ is positive semidefinite (PSD) given that $A$ is PSD and $B$ is arbitrary, where $A \in \mathbb{R}^{n \times n}$ and $B \in \mathbb{R}^{m \times n}$.

Here's how to approach the problem:

1. Use the definition of a PSD matrix: A matrix $C$ is PSD if for any vector $x$, $x^T C x \geq 0$.

2. Apply this definition to $BAB^T$: Let $y$ be any vector in $\mathbb{R}^m$, then we need to show that $y^T (BAB^T) y \geq 0$.

3. Expand using matrix multiplication: The expression becomes $y^T BAB^T y$.

4. Rearrange the expression: Since matrix multiplication is associative, we can write this as $(B^T y)^T A (B^T y)$.

5. Recognize that $B^T y$ is a vector in $\mathbb{R}^n$: Let's denote $z = B^T y$, which is a valid vector in $\mathbb{R}^n$ since $B$ has $n$ columns.

6. Apply the fact that $A$ is PSD: Since $A$ is PSD, it follows that for any vector $z$, $z^T A z \geq 0$.

7. Conclude the proof: Since $z = B^T y$ and $z^T A z \geq 0$ for any $y$, we can conclude that $y^T (BAB^T) y = (B^T y)^T A (B^T y) \geq 0$ for any $y$. Thus, $BAB^T$ is PSD.

So, regardless of what $B$ is, as long as $A$ is PSD, the matrix $BAB^T$ will also be PSD. This is because the product $z^T A z$ will always be non-negative due to the properties of $A$, and $z$ is simply the result of transforming $y$ by $B^T$, which does not affect the non-negativity of $z^T A z$.