# 瑞利商

Rayleigh quotient

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

## Main idea

Let $A$ be an $n\times n$ real symmetric matrix with eigenvalues $\lambda_1 \leq \cdots \leq \lambda_n$.
According to the spectral theorem, there is an orthonormal basis $\beta = \{\bv_1, \ldots, \bv_n\}$ corresponding to $\lambda_1,\ldots,\lambda_n$.

Let $\bv$ be a vector in $\mathbb{R}^n$.
Then we have the following properties:

- It can be written as $\bx = c_1\bv_1 + \cdots + c_n\bv_n$ for some coefficients $c_1,\ldots,c_n$.
- $\|\bx\|^2 = \inp{\bx}{\bx} = c_1^2 + \cdots + c_n^2$.
- $\bx\trans A\bx = \inp{A\bx}{\bx} = c_1^2\lambda_1 + \cdots + c_n^2\lambda_n$.

With these property in mind, one may solve the optimization problem:

minimize $\bx\trans A\bx$,
subject to $\|\bx\| = 1$.

The minimum value is $\lambda_1$ and is achieved by $\bx = \bv_1$ (or other vector in the same eigenspace).
Similarly, if the problem is asking for an maximum value,
then the maximum value is $\lambda_n$ and is achieved by $\bx = \bv_n$.

Let $A$ be an $n\times n$ real symmetric matrix.
The **Rayleigh quotient** of $A$ is a function of the form

$$
R_A(\bx) = \frac{\bx\trans A\bx}{\bx\trans \bx}.
$$

##### Rayleigh quotient theorem

Let $A$ be an $n\times n$ real symmetric matrix. Then

$$
\begin{aligned}
\lambda_1 &= \min_{ \substack{\bx\in\mathbb{R}^n \\ \bx\neq\bzero} } R_A(\bx) = \min_{ \substack{\bx\in\mathbb{R}^n \\ \|\bx\| = 1} } \bx\trans A\bx, \\
\lambda_n &= \max_{ \substack{\bx\in\mathbb{R}^n \\ \bx\neq\bzero} } R_A(\bx) = \max_{ \substack{\bx\in\mathbb{R}^n \\ \|\bx\| = 1} } \bx\trans A\bx.
\end{aligned}
$$

The minimum is achieved by an eigenvector of $\lambda_1$, while the maximum is achieved by an eigenvector of $\lambda_n$.

Moreover, if one already know $\lambda_1$ and $\bv_1$, then

$$
\lambda_2 = \min_{ \substack{\bx\in\mathbb{R}^n \\ \bx\neq\bzero,\ \bx\perp\bv_1} } R_A(\bx) = \min_{ \substack{\bx\in\mathbb{R}^n \\ \|\bx\| = 1,\ \bx\perp\bv_1} } \bx\trans A\bx.
$$

The vector $\bv_{n-1}$ can be done in a similar way if $\lambda_n$ and $\bv_n$ is known.

## Side stories

- optimization problem
- Courant–Fisher theorem

## Experiments

##### Exercise 1

執行以下程式碼。

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

### code
set_random_seed(0)
print_ans = False

n = 3
eigs = random_int_list(n)
A = diagonal_matrix(eigs)

pretty_print(LatexExpr("A ="), A)
        
if print_ans:
    xAx = " + ".join("x_%s^2 (%s)"%(i+1, eigs[i]) for i in range(n))
    print("xT A x =", xAx)
    print("max value:", max(eigs))
    print("achieved by:", identity_matrix(n)[max(list(range(n)), key=lambda k: eigs[k])])
    print("min value:", min(eigs))
    print("achieved by:", identity_matrix(n)[min(list(range(n)), key=lambda k: eigs[k])])

##### Exercise 1(a)

令

$$
\bx = \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix}.
$$

計算 $\bx\trans A\bx$。

<!-- eng start -->
Let

$$
\bx = \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix}.
$$

Find $\bx\trans A\bx$.
<!-- eng end -->

##### Exercise 1(b)

求 $\bx\trans A\bx$ 在 $\|\bx\| = 1$ 限制下的最大值。
達成這個最大值的 $\bx$ 為何？

<!-- eng start -->
Subject to $\|\bx\| = 1$, find the maximum of $\bx\trans A\bx$. What is the $\bx$ that achieves the maximum?
<!-- eng end -->

##### Exercise 1(c)

求 $\bx\trans A\bx$ 在 $\|\bx\| = 1$ 限制下的最小值。
達成這個最小值的 $\bx$ 為何？

<!-- eng start -->
Subject to $\|\bx\| = 1$, find the minimum of $\bx\trans A\bx$. What is the $\bx$ that achieves the minimum?
<!-- eng end -->

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

...
:::

## Exercises

##### Exercise 2

令 $A = \begin{bmatrix} a_{ii} \end{bmatrix}$ 為一 $n\times n$ 實對稱矩陣，且其特徵值為 $\lambda_1 \leq \cdots \leq \lambda_n$。

<!-- eng start -->
Let $A = \begin{bmatrix} a_{ii} \end{bmatrix}$ be an $n\times n$ real symmetric matrix with eigenvalues $\lambda_1 \leq \cdots \leq \lambda_n$.
<!-- eng end -->

##### Exercise 2(a)

證明對所有 $i = 1,\ldots,n$ 都有 $\lambda_1 \leq a_{ii} \leq \lambda_n$。

提示：找一個適合的向量 $\bx$ 來套用 $\lambda_1 \leq R_A(\bx) \leq \lambda_n$。

<!-- eng start -->
Show that $\lambda_1 \leq a_{ii} \leq \lambda_n$ for each $i = 1,\ldots,n$.

Hint: Find an appropriate vector $\bx$ for the inequality $\lambda_1 \leq R_A(\bx) \leq \lambda_n$.
<!-- eng end -->

##### Exercise 2(b)

令

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

說明 $A$ 的最大特徵值 $\lambda_3 \geq 2$。

<!-- eng start -->
Let

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

Show that the maximum eigenvalue of $A$ has $\lambda_3 \geq 2$.
<!-- eng end -->

##### Exercise 3

令 $A = \begin{bmatrix} a_{ii} \end{bmatrix}$ 為一 $n\times n$ 實對稱矩陣，且其特徵值為 $\lambda_1 \leq \cdots \leq \lambda_n$。

<!-- eng start -->
Let $A = \begin{bmatrix} a_{ii} \end{bmatrix}$ be an $n\times n$ real symmetric matrix with eigenvalues $\lambda_1 \leq \cdots \leq \lambda_n$.
<!-- eng end -->

##### Exercise 3(a)

證明 $\lambda_1 \leq \frac{1}{n} \sum_{i=1}^n\sum_{j=1}^n a_{ij} \leq \lambda_n$。

<!-- eng start -->
Show that $\lambda_1 \leq \frac{1}{n} \sum_{i=1}^n\sum_{j=1}^n a_{ij} \leq \lambda_n$.
<!-- eng end -->

##### Exercise 3(b)

令

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

說明 $A$ 的最大特徵值 $\lambda_3 \geq \frac{4}{3}$。

<!-- eng start -->
Let

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

Show that the maximum eigenvalue of $A$ has $\lambda_3 \geq \frac{4}{3}$.
<!-- eng end -->

##### Exercise 4

令 $A$ 為一 $n\times n$ 實對稱矩陣，且其特徵值為 $\lambda_1 \leq \cdots \leq \lambda_n$。
令 $B$ 為 $A$ 刪掉第一行第一列的矩陣，而其特徵值為 $\mu_1 \leq \cdots \leq \mu_{n-1}$。
證明 $\lambda_1 \leq \mu_1$ 且 $\mu_{n-1} \leq \lambda_n$。

<!-- eng start -->
Let $A$ be an $n\times n$ real symmetric matrix with eigenvalues $\lambda_1 \leq \cdots \leq \lambda_n$. Let $B$ be the matrix obtained from $A$ by removing its first row and column, and let $\mu_1 \leq \cdots \leq \mu_{n-1}$ be its eigenvalues. Show that $\lambda_1 \leq \mu_1$ and $\mu_{n-1} \leq \lambda_n$.
<!-- eng end -->

##### Exercise 5

令

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

解以下極值問題：

maximize $\bx\trans A \bx$,
subject to $\|\bx\| = 1$.

<!-- eng start -->
Let

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

Solve the optimization problem:

maximize $\bx\trans A \bx$,
subject to $\|\bx\| = 1$.
<!-- eng end -->

##### Exercise 6

已知

$$
A_n = \begin{bmatrix}
0 & 1 & ~ & 0 \\
1 & 0 & \ddots & ~ \\
~ & \ddots & \ddots & 1 \\
0 & ~ & 1 & 0
\end{bmatrix}
$$

的所有特徵值為 $\{2\cos(\frac{2k\pi}{n+1}): k = 1,\ldots, n\}$。

求在 $x_1^2 + \cdots + x_n^2 = 1$ 的限制下，
$x_1x_2 + x_2x_3 + \cdots + x_{n-1}x_n$ 的最大值為何。

<!-- eng start -->
It is known that

$$
A_n = \begin{bmatrix}
0 & 1 & ~ & 0 \\
1 & 0 & \ddots & ~ \\
~ & \ddots & \ddots & 1 \\
0 & ~ & 1 & 0
\end{bmatrix}
$$

has the spectrum $\{2\cos(\frac{2k\pi}{n+1}): k = 1,\ldots, n\}$.

Subject to $x_1^2 + \cdots + x_n^2 = 1$, find the maximum of $x_1x_2 + x_2x_3 + \cdots + x_{n-1}x_n$.
<!-- eng end -->

##### Exercise 7

令

$$
L = \begin{bmatrix}
2 & -1 & -1 \\
-1 & 1 & 0 \\
-1 & 0 & 1
\end{bmatrix}.
$$

解以下極值問題：

minimize $\bx\trans L \bx$,
subject to $\|\bx\| = 1$ and $\bx = \bone$.

這裡 $\bone$ 為全一向量。

<!-- eng start -->
Let

$$
L = \begin{bmatrix}
2 & -1 & -1 \\
-1 & 1 & 0 \\
-1 & 0 & 1
\end{bmatrix}.
$$

Solve the optimization problem:

minimize $\bx\trans L \bx$,
subject to $\|\bx\| = 1$ and $\bx = \bone$.
<!-- eng end -->

##### Exercise 8

查找各種資源，並描述柯朗–費雪定理（Courant–Fischer Theorem）。

<!-- eng start -->
Use any resource you prefer, state the Courant–Fischer Theorem.
<!-- eng end -->