---
title: Hoffman ratio bound in 白話文
categories: practice
date: 2022/3/16
authors: 李翊誠
breaks:
spicy:
tags: LA-Tea
---

{%hackmd 5xqeIJ7VRCGBfLtfMi0_IQ %}

<style>
#theorem{
background-color:rgb(230, 230, 230);
border: 2px solid rgb(100, 100, 100);
border-radius: 6px;
}
</style>

:::warning

- [x] "頗重要" 是一個贅詞，可以給一些比較明確敘述，比如說：一個連結圖獨立數和相鄰矩陣最小特徵值的不等式
:::

## 詳細解說 Hoffman ratio bound 及其證明

### 前言與定理敘述

在譜圖論（spectral graph theory）中，有一個描述連結圖獨立數和相鄰矩陣最小特徵值之間的不等式 &mdash; Hoffman ratio bound，或稱 Hoffman&ndash;Delsarte inequality：

<div id="theorem">

Suppose that $G$ is a $k$-regular graph, then
$$
\alpha(G) \leq \frac{n}{1-\frac{k}{\lambda_n}}
$$
</div>

:::warning
- [x] independent set --> 獨立集（independent set）；第一次用括號說明英文，之後都改成中文
- [x] $\lambda_{min}$ --> $\lambda_\text{min}$；後面的 $\lambda_{max}$ 也改一下
- [x] 翻譯明確的沒必要用英文，像是點（vertex）、度數（degree）
- [x] k-regular graph --> $k$-regular graph
- [x] 尋找獨立集（independent set）的大小在譜圖論之中是其中一個重要的課題 <-- 譜圖論 改成 圖論
- [x] 但大多數時候我們並沒有辦法精確找出它的大小 --> 但要求出它的精確值是一個 NP-問題
- [x] ，但我們可以使用一些不等式 --> 。然而、我們可以使用一些不等式
:::

其中有許多符號及定義，我們先一一解釋：

* $\alpha(G)$，在圖 $G$ 之中最大的獨立集（[independent set](https://zh.wikipedia.org/wiki/%E7%8B%AC%E7%AB%8B%E9%9B%86)）的大小，何謂獨立集？是指在 $G$ 的點集合中的一子集合，且兩個在該子集合的元素 $a,b$ 在圖中不相連。
* 我們定義 $\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_n$ 為 $G$ 所表示的鄰接矩陣（[adjacency matrix](https://en.wikipedia.org/wiki/Adjacency_matrix)）的特徵值，其中 $\lambda_n$ 為其最小的特徵值。
* $\text{regular graph}$，指的是該圖之中的每個點都有相同的度數，$k\text{-regular graph}$ 尤指每個點的度數都為 $k$。

尋找獨立集的大小在圖論之中是其中一個重要的課題，但要求出它的精確值是一個 NP-問題。然而、我們可以使用一些不等式將其壓在特定數值之下，而 Hoffman ratio bound 就是其中一個方式。

### 證明
在證明整個定理之前，我們需先知道一個小背景知識：

<div id="theorem">

While $G$ is a connect graph,
$$
\text{$G$ is $k$-regular graph} \implies |\lambda_1| = k.
$$
</div>

:::warning

- [x] 括號裡英文不用大寫，實際上第二次講到鄰接矩陣的時候就不用再給英文和連結了
:::

其中提醒一下 $\lambda_1$ ，是指 $G$ 所表示的鄰接矩陣（adjacency matrix）的最大特徵值。

:::warning

- [x] 中英文之間空格
- [x] $\max$ 的下標是不是 $i = 1$？
:::

我麼先說明這個背景小知識，令：
* $A$ 為圖 $G$ 的鄰接矩陣。
* $\bx$ 為 $A$ 的一特徵向量，且 $\bx$ 所對應的特徵值為$\lambda_1$。
* $x_j$ 為 $\bx$ 之中絕對值最大的元素，即 $x_j = \max_{i=0}^{n}|x_i|$。

我們可以透過以下不等式來說明：

$$
|\lambda_1||x_j| = |(A\bx)_j| = \left|\sum_{i, v_i\in N(v_j)} x_i\right| \leq \deg(v_j)|x_j| = k |x_j|
$$
其中 $N(v_j)$ 代表點 $v_j$ 的鄰居，$\deg(v_j)$ 代表點 $v_j$ 的度數。
:::warning

- [x] row 用中文
- [x] 做為 --> 作為
- [x] $0$ 和 $1$ 都要進數學模式
- [x] 說明 $N(v_j)$ 以及 $\deg$ 等符號
:::

1. 第一個等於只是簡單地單看 $A\bx$ 的第 $j$ 項，也就是單獨將 $A$ 的第 $j$ 列與 $\bx$ 內積相乘。
2. 而 $A$ 作為一圖的鄰接矩陣，其中不是 $0$ 就是 $1$、第 $j$ 列中為 1 的位址代表的即是圖 $G$ 中與 $v_j$ 相連的點。
3. 因此將會有 $\deg v_j$ 個元素相加，但我們已令 $x_j$ 為 $\bx$ 之中絕對值最大的元素，因此我們可以寫做等式可被 $\deg(v_j)|x_j|$ 壓下。
4. 同時 $\deg(v_j)$ 就是 $k$，因此我們就有了以上的不等式。

:::warning

- [x] 以上幾點說明了 $|\lambda_{max}| \le k$。
- [x] 因為確實存在一特徵向量，也就是全一向量 $\bone$，使得 $A\bone = k\bone$，而其對應的特徵值剛好就是 $k$。
:::

以上幾點說明了 $|\lambda_1| \le k$，但實際上，我們可以說 $\lambda_1 = k$，因為確實存在一特徵向量，也就是全一向量 $\bone$，使得 $A\bone = k\bone$，而其對應的特徵值剛好就是 $k$。
$$\bd=\begin{pmatrix}
1\\
1\\
\vdots\\
1
\end{pmatrix},
A\bd = k\bd$$
$\bd$ 的特徵值正是 $k$。

---

:::warning

- [x] 上面用 $\lambda_\text{min}$ 下面用 $\lambda_n$ 很怪，我建議把上面的都改成 $\lam
:::

之後我們就可以解釋 Hoffman-Delsarte inequality 的核心部分，首先我們先定義：

- $J_n$ 為 $n\times n$ 的全 $1$ 矩陣
- $\lambda_n$ 為 $A$ 最小的特徵值

我們寫兩個矩陣：
$$A,\quad \frac{k-\lambda_n}{n}J_n$$
注意這邊 $A$ 和 $J_n$ 各自都可以對角化，且 $AJ_n = J_nA$ 則存在一可逆矩陣 $S$ 使得 $S^{-1}AS$ 和 $S^{-1}J_nS$ 均為對角矩陣，也就是說 $A$ 和 $J_n$ 有相同的特徵向量集，我們稱 $A$ 和 $J_n$ 可同時對角化（[simultaneously diagonalizable](https://en.wikipedia.org/wiki/Diagonalizable_matrix#Simultaneous_diagonalization)）。接著我們令相同的特徵向量集為 $V$，任何 $V$ 中的特徵向量 $\bv$ 也是 矩陣 $A-J_n$ 的特徵向量，因為：
$$(A-J_n)\bv = A\bv - J_n\bv = \lambda_A\bv - \lambda_{J_n}\bv = (\lambda_A - \lambda_{J_n})\bv$$
其中，$\lambda_A$ 代表 $A$ 的某一個特徵值、$\lambda_{J_n}$ 代表 $J_n$ 的某一個特徵值，也就是說我們可以透過相減一些 $A$ 的特徵值與 $J_n$ 來得到新的矩陣 $(A-J_n)$ 的特徵值。

但我們怎麼知道哪一個特徵值對應到哪個特徵值呢?

我們知道全為 $1$ 的矩陣 $J_n$ 的特徵值只有兩個 $n$、$0$，重數分別為 $1$ 和 $n-1$，而矩陣$\frac{k-\lambda_n}{n}J_n$ 的特徵值則為 $k-\lambda_n$ 和 $0$。
$$\text{let }\bd=\begin{pmatrix}
1\\
1\\
\vdots\\
1
\end{pmatrix},\quad
A\bd = k\bd,\quad
\frac{k-\lambda_n}{n}J_n\bd=(k-\lambda_n)\bd$$
$A$ 之中特徵值 $k$ 對應到的是 $\frac{k-\lambda_n}{n}J_n$ 之中的 $(k-\lambda_n)$，其餘的特徵值對應到的都是 $0$，因此我們可以重組出新矩陣的全部特徵值，令 $A$ 的特徵值由大到小為 $\lambda_1,\lambda_2,\dots,\lambda_n$

$$\begin{align}
\spec(A - \frac{k-\lambda_n}{n}J_n) &= \{\lambda_1-(k-\lambda_n),\lambda_2-0,\lambda_3-0,\dots,\lambda_n-0\}\\
&=\{k-k+\lambda_n, \lambda_2,\dots, \lambda_n\}\\
&=\{\lambda_n, \lambda_2,\dots, \lambda_n\}
\end{align}$$
之中最小的特徵值確定為 $\lambda_n$。
接著我們定義矩陣 $E$

$$E = A - \frac{k-\lambda_n}{n}J_n - \lambda_nI_n$$

這麼做可以將所以特徵值統一減去 $\lambda_n$，保證了 $E$ 必為半正定（Positive semi-definite）。
給定原圖 $G$ 之中最大的 independent set $S$，$S$ 的大小為 $\alpha$，在 $E$ 之中單獨取出第 $i$ row 和第 $i$ column 的 $\alpha\times\alpha$ 子矩陣 $E_\alpha$
$$E_\alpha = E_{\{i,v_i\in S\}} = -\frac{k-\lambda_n}{n}J_\alpha - \lambda_n I_\alpha$$ 是矩陣 $E$ 的一個主子矩陣（principal submatrix）
如下舉例：
$$\text{if } E =\begin{bmatrix}
2 & 4 & 1 & 3 & 0\\
4 & 6 & 2 & 1 & 2\\
1 & 2 & 7 & 3 & 0\\
3 & 1 & 3 & 9 & 3\\
0 & 2 & 0 & 3 & 2\\
\end{bmatrix}
,\text{then }
E_{\{2,4,5\}}=\begin{bmatrix}
6 & 1 & 2\\
1 & 9 & 3\\
2 & 3 & 2\\
\end{bmatrix}$$

而一個半正定矩陣的主子矩陣也會是半正定，不過現在的 $E_\alpha$ 僅由 $J_\alpha$ 和 $I_\alpha$ 組成，我們能夠直接推導出他的特徵值了。

$$\spec(-\frac{k-\lambda_n}{n}J_\alpha)=\{-\alpha\frac{k-\lambda_n}{n},0\}$$
$$\spec(E_\alpha)=\spec(-\frac{k-\lambda_n}{n}J_\alpha - \lambda_n I_\alpha)=
\{-\alpha\frac{k-\lambda_n}{n}-\lambda_n,0-\lambda_n\}\\
=\{-\alpha\frac{k-\lambda_n}{n}-\lambda_n,-\lambda_n\}$$

且半正定矩陣的所有特徵值均 $\ge0$，因此：
$$\begin{align}
-\alpha\frac{k-\lambda_n}{n}-\lambda_n\ge0 &
\implies -\alpha\frac{k-\lambda_n}{n} \ge \lambda_n\\
&\implies \alpha\frac{k-\lambda_n}{n} \le -\lambda_n\\
&\implies \alpha \le \frac{-n\lambda_n}{k-\lambda_n}\\
&\implies \alpha \le \frac{n}{1-\frac{k}{\lambda_n}}
\end{align}_\square$$
到此我們就證明完了 Hoffman ratio bound。