# 正定與半正定矩陣

Positivity

This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).

$\newcommand{\trans}{^\top}
\newcommand{\adj}{^{\rm adj}}
\newcommand{\cof}{^{\rm cof}}
\newcommand{\inp}[2]{\left\langle#1,#2\right\rangle}
\newcommand{\dunion}{\mathbin{\dot\cup}}
\newcommand{\bzero}{\mathbf{0}}
\newcommand{\bone}{\mathbf{1}}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\nul}{\operatorname{null}}
\newcommand{\rank}{\operatorname{rank}}
%\newcommand{\ker}{\operatorname{ker}}
\newcommand{\range}{\operatorname{range}}
\newcommand{\Col}{\operatorname{Col}}
\newcommand{\Row}{\operatorname{Row}}
\newcommand{\spec}{\operatorname{spec}}
\newcommand{\vspan}{\operatorname{span}}
\newcommand{\Vol}{\operatorname{Vol}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\idmap}{\operatorname{id}}
\newcommand{\am}{\operatorname{am}}
\newcommand{\gm}{\operatorname{gm}}
\newcommand{\mult}{\operatorname{mult}}
\newcommand{\iner}{\operatorname{iner}}$

from lingeo import random_int_list, random_good_matrix
from sym import inertia

## Main idea

A real symmetric matrix $A$ is said to be **positive definite** or **positive semidefinite** if

$$
\bx\trans A\bx > 0 \quad\text{ or }\quad \bx\trans A\bx \geq 0,
$$

respectively, for any nonzero vector $\bx$.

A matrix $A$ is **negative definite** or **negative semidefinite** if $-A$ is positive definite or positive semidefinite, respectively.

##### Remark

In general, only positivity of a matrix only focus on real symmetric matrices (or complex Hermitian matrices).
That is, when we say a matrix is positive (semi)definite, we automatically assume it is symmetric.

It is known that a matrix $A$ is positive definite if and only if all its eigenvalues are positive.
Similarly, $A$ is positive semidefinite if and only if all its eigenvalues are nonnegative.
Note that an $n\times n$ positive semidefinite matrix $A$ is positive definite if and only if $\rank(A) = n$.

Let $A$ be an $n\times n$ positive semidefinite matrix of $\rank(A) = k$.
One may diagonalize it as $A = QDQ\trans $ by some orthogonal matrix $Q$ and diagonal matrix $D$.
Let $\lambda_1,\ldots,\lambda_k$ be the nonzero eigenvalues of $A$.
Then we have

$$
A = Q\begin{bmatrix}
\lambda_1 & ~ & ~ & ~ \\
~ & \ddots & ~ & O_{r,n-r} \\
~ & ~ & \lambda_r & ~ \\
~ & O_{n-r,r} & ~ & O_{n-r,n-r}
\end{bmatrix} Q\trans =
Q\begin{bmatrix}
\sqrt{\lambda_1} & ~ & ~ \\
~ & \ddots & ~ \\
~ & ~ & \sqrt{\lambda_r} \\
~ & O_{n-r,r} & ~
\end{bmatrix}\begin{bmatrix}
\sqrt{\lambda_1} & ~ & ~ & ~ \\
~ & \ddots & ~ & O_{r,n-r} \\
~ & ~ & \sqrt{\lambda_r} & ~ \\
\end{bmatrix} Q\trans = MM\trans
$$

for some $k\times n$ matrix $M$.

If a matrix $A$ can be written as $A = MM\trans$ for some matrix $M$, then $A$ is called a **Gram** matrix.
If $\br_1,\ldots,\br_n$ are the rows of $M$, then this means $A$ is a matrix of inner products;
that is, $A = \begin{bmatrix} \inp{\br_i}{\br_j} \end{bmatrix}$.

Indeed, a matrix is a Gram matrix if and only if it is positive semidefinite.

## Side stories

- square root of a matrix
- inner product space

## Experiments

##### Exercise 1

執行以下程式碼。

<!-- eng start -->
Run the code below.
<!-- eng end -->

### code
set_random_seed(0)
print_ans = False

n = 3
while True:
    eigs = random_int_list(n, 1)
    if not all(eig == 0 for eig in eigs):
        break
Q = random_good_matrix(n,n,n,2)
A = Q * diagonal_matrix(eigs) * Q.transpose()

pretty_print(LatexExpr("A ="), A)
print("eigenvalues =", A.eigenvalues())
        
if print_ans:
    iner = inertia(A)
    if iner[0] > 0:
        while True:
            x = vector(random_int_list(n))
            if x.inner_product(A * x) > 0:
                break
    if iner[1] > 0:
        while True:
            y = vector(random_int_list(n))
            if y.inner_product(A * y) < 0:
                break
    if iner[1] == 0:
        if iner[2] == 0:
            print("positive definite")
        if iner[2] > 0:
            print("positive semidefinite")
        print("x =", x)
    if iner[0] == 0:
        if iner[2] == 0:
            print("negative definite")
        if iner[2] > 0:
            print("negative semidefinite")
        print("y =", y)
    if iner[0] > 0 and iner[1] > 0:
        print("none above")
        print("x =", x)
        print("y =", y)

##### Exercise 1(a)

判斷 $A$ 是否為正定、半正定、負定、半負定、或是皆不是。

<!-- eng start -->
Determine whether $A$ is positive definite, positive semidefinite, negative definite, negative semidefinite, or none of above.
<!-- eng end -->

##### Exercise 1(b)

若 $A$ 為正定或半正定，找一個非零向量 $\bx$ 使得 $\bx\trans A\bx > 0$。
若 $A$ 為負定或半負定，找一個非零向量 $\by$ 使得 $\by\trans A\by < 0$。
若以上皆不是，找兩個非零向量 $\bx$ 和 $\by$ 使得 $\bx\trans A\bx > 0$ 而 $\by\trans A\by < 0$。

<!-- eng start -->
If $A$ is positive definite or positive semidefinite, find a nonzero vector $\bx$ such that $\bx\trans A\bx > 0$. If $A$ is negative definite or negative semidefinite, find a nonzero vector $\bx$ such that $\bx\trans A\bx < 0$. If $A$ belongs to none of the above categories, find nonzero vectors $\bx$ and $\by$ such that $\bx\trans A\bx > 0$ and $\by\trans A\by < 0$.
<!-- eng end -->

:::info
What do the experiments try to tell you? (open answer)

...
:::

## Exercises

##### Exercise 2

判斷以下矩陣是否為正定、半正定、皆不是。

<!-- eng start -->
For each of the following matrices, determine whether it is positive definite, positive semidefinite, or none of above.
<!-- eng end -->

##### Exercise 2(a)

$$
A = \begin{bmatrix}
2 & 1 \\
1 & 2
\end{bmatrix}.
$$

**[由蔡睿丞提供]**
Suppose $Q = \begin{bmatrix}
x \\
y
\end{bmatrix}$, then $\ Q \trans = \begin{bmatrix}
x & y \end{bmatrix}$.
$\ Q\trans AQ = \begin{bmatrix}
x & y
\end{bmatrix} \begin{bmatrix}
2 & 1 \\
1 & 2
\end{bmatrix} \begin{bmatrix}
x \\
y \end{bmatrix} = \ (x+y)^2 + \ x^2 + \ y^2$,
We know that $\ (x+y)^2 + \ x^2 + \ y^2>0$ when $(x,y) \neq \bzero$,
Thus, $A$ is positive definite.

##### Exercise 2(b)

$$
A = \begin{bmatrix}
0 & 1 \\
1 & 0
\end{bmatrix}.
$$

**[由蔡睿丞提供]**
Suppose $Q = \begin{bmatrix}
x \\
y
\end{bmatrix}$, then$\ Q \trans = \begin{bmatrix}
x & y \end{bmatrix}$。
$\ Q\trans AQ = \begin{bmatrix}
x & y
\end{bmatrix} \begin{bmatrix}
0 & 1 \\
1 & 0
\end{bmatrix} \begin{bmatrix}
x \\
y \end{bmatrix} = \ 2xy$，
When $\begin{bmatrix}
x \\
y
\end{bmatrix}=\begin{bmatrix}
1 \\
0 \end{bmatrix}$, then $\ 2xy = 0$， When $\begin{bmatrix}
x \\
y
\end{bmatrix}=\begin{bmatrix}
1 \\
-1 \end{bmatrix}$, then $\ 2xy = -2$
Thus, $A$ is none of above.

##### Exercise 2(c)

$$
A = \begin{bmatrix}
1 & 1 & 1 \\
1 & 1 & 1 \\
1 & 1 & 1 \\
\end{bmatrix}.
$$

**[由蔡睿丞提供]**
Suppose $Q = \begin{bmatrix}
x \\
y \\
z
\end{bmatrix}$， then $\ Q \trans = \begin{bmatrix}
x & y & z \end{bmatrix}$。
$\ Q\trans AQ = \begin{bmatrix}
x & y & z
\end{bmatrix} \begin{bmatrix}
1 & 1 & 1 \\
1 & 1 & 1 \\
1 & 1 & 1
\end{bmatrix} \begin{bmatrix}
x \\
y \\
z \end{bmatrix} = \ x^2 + y^2 + z^2 + 2xy +2xz +2yz = (x+y+z)^2$
when $Q = \begin{bmatrix}
x \\
y \\
z
\end{bmatrix}=\begin{bmatrix}
1 \\
-1\\
0 \end{bmatrix}$ or $\begin{bmatrix}
-1 \\
1\\
0 \end{bmatrix}$ or $\begin{bmatrix}
1 \\
0\\
-1 \end{bmatrix}$, then $(x+y+z)^2 = 0$
Thus, $A$ is positive semidefinite.

##### Exercise 3

令 $A = \begin{bmatrix} a_{ij} \end{bmatrix}$ 為 $n\times n$ 一正定矩陣。

<!-- eng start -->
Let $A = \begin{bmatrix} a_{ij} \end{bmatrix}$ be an $n\times n$ positive definite matrix.
<!-- eng end -->

##### Exercise 3(a)

證明對於所有 $i$ 都有 $a_{ii} \geq 0$。

<!-- eng start -->
Show that $a_{ii} \geq 0$ for each $i$.
<!-- eng end -->

##### Exercise 3(b)

證明

$$
\sum_{i=1}^n\sum_{j=1}^n a_{ij} \geq 0.
$$

<!-- eng start -->
Show that

$$
\sum_{i=1}^n\sum_{j=1}^n a_{ij} \geq 0.
$$
<!-- eng end -->

##### Exercise 4

證明以下關於（半）正定矩陣的相關性質。

<!-- eng start -->
Prove the following properties of positive (semi)definite matrices.
<!-- eng end -->

##### Exercise 4(a)

正定矩陣的主子矩陣也是正定矩陣。

<!-- eng start -->
The principal submatrix of a positive definite matrix is again a positive definite matrix.
<!-- eng end -->

##### Exercise 4(b)

正定矩陣加半正定矩陣是正定矩陣、
而半正定矩陣加半正定矩陣是半正定矩陣。

<!-- eng start -->
The sum of a positive definite matrix and a positive semidefinite matrix is a positive definite matrix, while the sum of two positive semidefinite matrices is a positive semidefinite matrix.
<!-- eng end -->

##### Exercise 5

依照以下步驟證明以下敘述等價：

1. $A$ 是正定矩陣。
2. $A$ 的特徵值均為正。

<!-- eng start -->
Use the given instruction to show that the following are equivalent:

1. $A$ is a positive definite matrix.
2. Every eigenvalue of $A$ is positive.
<!-- eng end -->

##### Exercise 5(a)

證明若 $A$ 有一特徵值 $\lambda\leq 0$，則存在一個非零向量 $\bx$ 使得 $\bx\trans A\bx \leq 0$。
因此若 $A$ 正定，則 $A$ 的特徵值均為正。

<!-- eng start -->
Show that if $A$ has an eigenvalue $\lambda \leq 0$, then there is nonzero vector $\bx$ such that $\bx\trans A\bx \leq 0$. Therefore, if $A$ is positive definite, then every eigenvalue of $A$ is positive.
<!-- eng end -->

##### Exercise 5(b)

證明若 $A$ 的特徵值均為正，則對於所有非零向量 $\bx$ 都有 $\bx\trans A\bx > 0$。
（參考 607-3。）

<!-- eng start -->
Show that if every eigenvalue of $A$ is positive, then $\bx\trans A\bx > 0$ for any nonzero vector $\bx$. (See 607-3.)
<!-- eng end -->

##### Exercise 6

證明以下敘述等價：

1. $A$ 是半正定矩陣。
2. $A$ 是格拉姆矩陣。

<!-- eng start -->
Show that the following are equivalent.

1. $A$ is positive semidefinite.
2. $A$ is a Gram matrix.
<!-- eng end -->

##### Exercise 7

以下練習探討矩陣根號的概念。

<!-- eng start -->
The following exercises explore the notion of the square root of a matrix.
<!-- eng end -->

##### Exercise 7(a)

證明若 $A$ 是一正定矩陣，
則其可寫成 $A = M^2$，
其中 $M$ 是對稱矩陣。

<!-- eng start -->
Show that if $A$ is a positive definite matrix, then it can be written as $A = M^2$, where $M$ is a symmetric matrix.
<!-- eng end -->

##### Exercise 7(b)

若 $A$ 是一正定矩陣、$B$ 為一對稱矩陣，
證明 $AB$ 的特徵值均為實數。

提示：證明 $AB$ 和某對稱矩陣相似。

<!-- eng start -->
Suppose $A$ is a positive definite matrix and $B$ is a symmetric matrix. Show that every eigenvalue of $AB$ is real.

Hint: Show that $AB$ is similar to some symmetric matrix.
<!-- eng end -->

##### Exercise 8

回顧 213-5 中提到的廣義內積的定義。

以下練習說明廣義內積完全是由正定矩陣做出來的。

<!-- eng start -->
Recall the definition of an inner product in 213-5.

The following exercises show that any inner product is the quadratic form of some positive definite matrix.
<!-- eng end -->

##### Exercise 8(a)

令 $A$ 為一正定矩陣。
定義 $\inp{\bx}{\by}_A:=\by\trans A\bx$。

證明 $\inp{\cdot}{\cdot}_A$ 為一內積。

<!-- eng start -->
Let $A$ be a positive definite matrix. Define $\inp{\bx}{\by}_A:=\by\trans A\bx$. Show that $\inp{\cdot}{\cdot}_A$ is an inner product.
<!-- eng end -->

##### Exercise 8(b)

令 $\inp{\cdot}{\cdot}$ 為一內積，
找一個矩陣 $A$ 使得對所有向量 $\bx$ 和 $\by$ 都有 $\inp{\bx}{\by} = \by\trans A\bx$。
驗證這個矩陣必須是正定的。

提示：選一些特別的 $\bx$ 和 $\by$ 來找到 $A$ 的各項。

<!-- eng start -->
Let $\inp{\cdot}{\cdot}$ be an inner product. Find a matrix $A$ such that $\inp{\bx}{\by} = \by\trans A\bx$ for any vectors $\bx$ and $\by$. Verify that this matrix must be positive definite.

Hint: Substitute some particular $\bx$ and $\by$ to find the entries of $A$.
<!-- eng end -->