608-Positivity

$\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}}$

In [ ]:

from lingeo import random_int_list, random_good_matrix
from sym import inertia

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

Exercise 1¶

執行以下程式碼。

Run the code below.

In [ ]:

### 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$ 是否為正定、半正定、負定、半負定、或是皆不是。

Determine whether $A$ is positive definite, positive semidefinite, negative definite, negative semidefinite, or none of above.

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$。

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$.

Exercise 2¶

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

For each of the following matrices, determine whether it is positive definite, positive semidefinite, or none of above.

Exercise 2(a)¶

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

Exercise 2(b)¶

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

Exercise 2(c)¶

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

Exercise 3¶

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

Let $A = \begin{bmatrix} a_{ij} \end{bmatrix}$ be an $n\times n$ positive definite matrix.

Exercise 3(a)¶

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

Show that $a_{ii} \geq 0$ for each $i$.

Exercise 3(b)¶

證明

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

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

Exercise 4¶

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

Prove the following properties of positive (semi)definite matrices.

Exercise 4(a)¶

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

The principal submatrix of a positive definite matrix is again a positive definite matrix.

Exercise 4(b)¶

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

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.

Exercise 5¶

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

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

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.

Exercise 5(a)¶

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

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.

Exercise 5(b)¶

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

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

Exercise 6¶

證明以下敘述等價：

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

Show that the following are equivalent. 1. $A$ is positive semidefinite. 2. $A$ is a Gram matrix.

Exercise 7¶

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

The following exercises explore the notion of the square root of a matrix.

Exercise 7(a)¶

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

Show that if $A$ is a positive definite matrix, then it can be written as $A = M^2$, where $M$ is a symmetric matrix.

Exercise 7(b)¶

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

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

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.

Exercise 8¶

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

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

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.

Exercise 8(a)¶

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

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

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.

Exercise 8(b)¶

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

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

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$.

正定與半正定矩陣¶

Main idea¶