Circulant Matrix#

An $n \times n$ circulant matrix $\mathbf{C}$ takes the form

It has the determinant $\det(\mathbf{C}) = \displaystyle \prod_{i=0}^{n-1} f(\omega^i)$ , where $f(x) = c_0 + c_1 x + \cdots + c_{n-1} x^{n-1}$ and $\omega = e^{2\pi i/n}$.

Proof

Let $\mathbf{\Omega}=(\omega^{(i-1)(j-1)})_{1\leq i, j \leq n} \in \mathbf{\mathcal{M}}_n(\mathbb{C})$, then

$$\begin{aligned} \det(\mathbf{C}\mathbf{\Omega}) &= \det\left(\left[\begin{array}{cccc}f(1) & f(\omega) & \cdots & f(\omega^{n-1}) \\ f(1) & \omega f(\omega) & \cdots & \omega^{n-1} f(\omega^{n-1}) \\ \vdots & \vdots & \ddots & \vdots \\ f(1) & \omega^{n-1}f(\omega) & \cdots & \omega^{(n-1)(n-1)}f(\omega^{n-1}) \end{array}\right]\right) \\ \\ &=f(1)f(\omega)\cdots f(\omega^{n-1})\det(\mathbf{\Omega}) \\ &=\det(\mathbf{\Omega})\prod_{i=0}^{n-1} f(\omega^i) \end{aligned}$$

Therefore , $\det(\mathbf{C}) = \det(\mathbf{\Omega}) \displaystyle \prod_{i=0}^{n-1} f(\omega^i)$. $\quad \square$

Gridiant of Log-Determinant Function#

Let $\mathbf{X}\in \mathscr{S}_{++}$ be a positive definite matrix, then $\nabla (\log\det\mathbf{X})=\mathbf{X}^{-1}$.

Proof

Let $\mathbf{Y}=\mathbf{X}+\Delta \mathbf{X}$, then

$$\begin{aligned} \log\det\mathbf{Y} &= \log\det(\mathbf{X}^{\frac{1}{2}}(\mathbf{I}+\mathbf{X}^{-\frac{1}{2}}\Delta\mathbf{X}\mathbf{X}^{-\frac{1}{2}}X^{\frac{1}{2}})) \\ &= \log\det\mathbf{X} + \log\det(\mathbf{I}+\mathbf{X}^{-\frac{1}{2}}\Delta\mathbf{X}\mathbf{X}^{-\frac{1}{2}}) \\ &= \log\det\mathbf{X} + \sum_{i=1}^n \log(1+\lambda_i) \end{aligned}$$

where $\lambda_i$ are the eigenvalues of $\mathbf{X}^{-\frac{1}{2}}\Delta\mathbf{X}\mathbf{X}^{-\frac{1}{2}}$. Since $\mathbf{X}=\mathcal{o}(\mathbf{X})$, we have $\lambda_i = \mathcal{o}(1)$, and thus $\log(1+\lambda_i)=\lambda_i + \mathcal{o}(\lambda_i)$. Therefore

$$\begin{aligned} \log\det\mathbf{Y} &= \log\det\mathbf{X} + \sum_{i=1}^n \lambda_i + \mathcal{o}(1) \\ &=\log\det\mathbf{X}+\text{tr}(\mathbf{X}^{-\frac{1}{2}}\Delta\mathbf{X}\mathbf{X}^{-\frac{1}{2}}) + \mathcal{o}(1) \\ &=\log\det\mathbf{X}+\text{tr}(\mathbf{X}^{-1}\Delta\mathbf{X}) + \mathcal{o}(1) \end{aligned}$$

Thus, $\text{d}(\mathbf{X} \log\det\mathbf{X}) = \text{tr}(\mathbf{X}^{-1}\text{d}\mathbf{X})\Longrightarrow \nabla (\log\det\mathbf{X})=\mathbf{X}^{-1}$. $\quad \square$

Barbalat’s Lemma#

If $f:\mathbb{R^+} \rightarrow \mathbb{R^+}$ is uniformly continuous with $\displaystyle\int_a^{+\infty} f(t)dt < +\infty$, then $\displaystyle\lim_{t\rightarrow +\infty} f(t) = 0$.

For series we have $\displaystyle \sum_{n=1}^{+\infty} u_n < +\infty \Rightarrow \lim_{n\rightarrow +\infty} u_n = 0$. However, for functions $\displaystyle\int_a^{+\infty} f(t)dt < +\infty$$\nLeftrightarrow$ $\lim_{t\rightarrow +\infty} f(t) = 0$, the uniform continuity is necessary.

• Example 1. $f(x)=\sin(x^2)$
  Since $\displaystyle\int_1^{+\infty} \sin(x^2)dx \ \overset{\ u=x^2}{\xlongequal{}\xlongequal{}}\int_1^{+\infty} \frac{\sin(u)}{2\sqrt{u}}du$, by Dirichlet’s test, the integral converges. However, $\displaystyle \lim_{x\rightarrow +\infty} \sin(x^2)$ does not exist.
• Example 2. $\displaystyle f(x)=\frac{x}{1+x^6\sin^2x} > 0$
  Define $\displaystyle F(u)=\int_0^u f(x)dx$ and $\displaystyle a_k=\int_{(k-1)\pi}^{k\pi} f(x)dx$, then $F(u)$ is monotonic increasing on $\mathbb{R}^+$ and $\displaystyle F(n\pi)=\sum_{k=1}^{n}a_k$. We have $$\begin{aligned} a_k &\leq \int_{(k-1)\pi}^{k\pi} \frac{k\pi}{1+(k-1)^6\pi^6\sin^2x}dx \\ &= 2k\pi \int_0^{\frac{\pi}{2}} \frac{dx}{1+(k-1)^6\pi^6\sin^2x} \\ &\leq 2k\pi \int_0^{\frac{\pi}{2}} \frac{dx}{1+(k-1)^6\pi^6(\frac{2}{\pi} x)^2} \\ &= 2k\pi\int_0^{\frac{\pi}{2}} \frac{dx}{1+{[2(k-1)^3\pi^2x]}^2} \\ &= \frac{k}{(k-1)^3\pi}\int_0^{(k-1)^3\pi}\frac{dt}{1+t^2} \\ &\leq \frac{k}{(k-1)^3\pi}\int_0^{+\infty}\frac{dt}{1+t^2} \\ &=\frac{k}{2(k-1)^3} \underset{+\infty}{\sim} \frac{1}{2k^2} \end{aligned}$$ Here we use the inequality $\sin x \geq \frac{2x}{\pi}$ and the fact that $\displaystyle \int_0^{+\infty}\frac{dt}{1+t^2} = \frac{\pi}{2}$. Therefore, $\displaystyle \lim_{n\rightarrow +\infty} F(n\pi)$ exists. By $F(x)$ increasing, $\displaystyle \lim_{x\rightarrow +\infty} < +\infty$, but $\displaystyle\lim_{x\rightarrow +\infty} f(x)$ doesn’t exist.

Proof

If $f(x)\nrightarrow 0$ as $x\rightarrow +\infty$, then there exists $\epsilon>0$ and a sequence $(x_n)$ such that $\forall n\in \mathbb{N}, |f(x_n)|>\epsilon$. Since $f$ is uniformly continuous, $\exists \delta>0 \ \forall n\in\mathbb{N} \ \forall y>0, \ |x_n-y|<\delta \Rightarrow |f(x_n)-f(y)|<\frac{\epsilon}{2}$. So $\forall x\in[x_n, x_n+\delta]$, we have $|f(x)|>|f(x_n)|-|f(x_n)-f(y)|>\frac{\epsilon}{2}$. Therefore

$$\left|\int_a^{x_n+\delta} f(t)dt - \int_a^{x_n}f(t)dt\right| = \sum_{x_n}^{x_n+\delta} f(t)dt > \frac{\epsilon\delta}{2}>0$$

However, since $\displaystyle\int_0^{\infty} f(t)dt$ exists. LHS converges to 0 as $n\rightarrow +\infty$, yielding a contradiction. $\quad \square$ However, since $\int_0^{\infty} f(t)dt$ exists. LHS converges to 0 as $n\rightarrow +\infty$, yielding a contradiction. $\quad \square$

Perron-Frobenius Theorem#

Definition

Positive Matrix#

A positive(non-negative) matrix $\mathbf{A}\in \mathbf{\mathcal{M}}_{n,m}(\mathbb{R})$ is a matrix with all entries $a_{ij}$ positive(non-negative). If $\mathbf{A}>0, \mathbf{\alpha} \geq 0, \mathbf{\alpha}\neq 0$, then $\mathbf{A}\mathbf{\alpha}>0$.

Definition

Spectral Radius#

The spectral radius of a matrix $\mathbf{A}\in \mathbf{\mathcal{M}}_n(\mathbb{R})$ is defined as $\rho(\mathbf{A})=\max\{|\lambda|:\lambda \text{ is an eigenvalue of } \mathbf{A}\}$.

Let $\mathbf{A}\in \mathbf{\mathcal{M}}_n(\mathbb{R})$ be a positive matrix, then

1. $\mathbf{A}$ has a positive eigenvalue $\rho(\mathbf{A})$ with respect to a positive eigenvector $\mathbf{v}$ (Perron–Frobenius eigenvalue).
2. Perron–Frobenius eigenvalue is simple (i.e. the algebraic multiplicity of $\rho(\mathbf{A})$ is both 1).
3. There are no other positive eigenvectors except positive multiples of $\mathbf{v}$.

Lemma

Gelfand’s formula#

If $\mathbf{A}\in \mathbf{\mathcal{M}}_n(\mathbb{C})$ and $\mathbf{A}\neq 0$, then $\displaystyle \rho(\mathbf{A})=\lim_{k\rightarrow +\infty} ||\mathbf{A}^k||_2^{\frac{1}{k}}$ with $||\cdot||_2$ the spectral norm.

Proof

We can suppose that $\rho(\mathbf{A})=1$

1. Let $\lambda$ be an eigenvalue of $\mathbf{A}$ with $|\lambda|=1=\rho(\mathbf{A})$ and $\mathbf{v}$ the corresponding eigenvector. Consider $\mathbf{\alpha}=(|\mathbf{v}_i|)>0$, then we have

   $$\begin{aligned} (\mathbf{A}\mathbf{\alpha})_i &= \sum_j a_{ij}|\mathbf{v}_j| \geq |\sum_j a_{ij}\mathbf{v}_j| = |\lambda \mathbf{v}_i| \\ &= |\mathbf{v}_i| = |\lambda||\mathbf{v}_i| = |\mathbf{v}_i| \end{aligned}$$

   which implies $(\mathbf{A}\mathbf{\alpha})_i\geq |\mathbf{v}_i|\Rightarrow \mathbf{A}\mathbf{\alpha}\geq \mathbf{\alpha}$. Now we prove that $\mathbf{A}\mathbf{\alpha}>\mathbf{\alpha}$ is impossible. Suppose that $A\mathbf{\alpha}>\mathbf{\alpha}$, then

   $$\mathbf{A}\mathbf{\alpha}-\mathbf{\alpha}>0 \Rightarrow \mathbf{A}(\mathbf{A}-\mathbf{\alpha})>0 \Rightarrow \mathbf{A}^2\mathbf{\alpha}>\mathbf{A}\mathbf{\alpha}$$

   Thus, $\exists \epsilon>0 \ s.t. \ \mathbf{A}^2\mathbf{\alpha}>\mathbf{A}\mathbf{\alpha}(1+\epsilon)$, and by induction we have $\mathbf{A}^k\mathbf{\alpha}>\mathbf{A}^{k-1}\mathbf{\alpha}(1+\epsilon)^{k-1}$, which implies $||\mathbf{A}^k\mathbf{\alpha}||_2 > (1+\epsilon)^{k-1}||\mathbf{A}\mathbf{\alpha}||_2$. Therefore

   $$\lim_{k\rightarrow +\infty}||\mathbf{A}^k||_2^{\frac{1}{k}}\geq \left(\frac{||\mathbf{A}^k(\mathbf{A}\mathbf{\alpha})||_2}{||\mathbf{A}\mathbf{\alpha}||_2}\right)^{\frac{1}{k}} > 1+\epsilon > 1=\rho(\mathbf{A})$$

   which contradicts Gelfand’s formula. Therefore, $\mathbf{A}\mathbf{\alpha}=\mathbf{\alpha}>0$ which means there exists a positive eigenvector $\mathbf{\alpha}$ with respect to eigenvalue $\rho(\mathbf{A})$.

2. Assume that there exists an eigenvector $\mathbf{\beta}$ that is linearly independent with $\mathbf{\alpha}$ and corresponds to the eigenvalue $\rho(\mathbf{A})=1$. Let $c=\min_{\mathbf{\beta}_i>0} \frac{\mathbf{\alpha}_i}{\mathbf{\beta}_i}=\frac{\mathbf{\alpha}_k}{\mathbf{\beta}_k}$ (if $\beta<0$, we can choose $-\beta>0$), then we have $c>0$ and $\mathbf{\alpha}-c\mathbf{\beta}\geq 0, \mathbf{\alpha}-c\mathbf{\beta}\neq 0$. However, since $\mathbf{A}>0$, $\mathbf{\alpha}-c\mathbf{\beta}=\mathbf{A}(\mathbf{\alpha}-c\mathbf{\beta})>0$, which contradicts the fact that $\mathbf{\alpha}_k-c\mathbf{\beta}_k=0$. Therefore, the geometric multiplicity of $\rho(\mathbf{A})$ is 1.

   Using the fact that $\mathbf{A}^\mathsf{T}$ is also positive, there exists a positive eigenvector $\mathbf{\gamma}$ with respect to the eigenvalue $\rho(\mathbf{A}^\mathsf{T})=1$. Note $\mathcal{U}=\text{span}(\mathbf{\gamma})$, we have $\mathbb{R}^n=\mathcal{U}^\perp \oplus\mathcal{U}$. Since $\mathbf{\alpha}>0, \mathbf{\gamma}>0$, then $\mathbf{\gamma}^\mathsf{T}\mathbf{\alpha}>0\Rightarrow \mathbf{\alpha}\in\mathcal{U}$. Choose a basis $\mathcal{E}=(\mathbf{\alpha}, e_1, \cdots, e_{n-1})$ for $\mathbb{R}^n$, then the matrix of $\mathbf{A}$ under $\mathcal{E}$ is

   $$\left(\begin{array}{cc}1 & * \\ \mathbf{0} & \mathbf{B}\end{array}\right)$$

   If there exists a positive eigenvector $\mathbf{\delta}$ of $\mathbf{B}$ with respect to the eigenvalue $1$, then $\mathbf{\delta}\in\mathcal{U}^\mathsf{T}$, which implies $\mathbf{\delta}$ and $\mathbf{\alpha}$ are linearly dependent, contracting the fact that the geometric multiplicity is 1. Therefore, the algebraic multiplicity of $\mathbf{A}$ is also 1.

3. Suppose there exists a positive eigenvector $\mathbf{\beta}$ corresponding to the eigenvalue $\lambda < 1$, then by the positivity of $\mathbf{A}$, $\lambda>0$. Let $c=\max \frac{\mathbf{\alpha}_i}{\mathbf{\beta}_i}=\frac{\mathbf{\alpha}_k}{\mathbf{\beta}_k}$, then $c\mathbf{\beta}-\mathbf{\alpha}\geq 0, c\mathbf{\beta}-\mathbf{\alpha}\neq 0$. However, since $\mathbf{A}>0$, $\lambda c\mathbf{\beta}-\mathbf{\alpha}=\mathbf{A}(c\mathbf{\beta}-\mathbf{\alpha})>0$, which means $\forall i\in[[1, n]] ~~ \lambda c\mathbf{\beta}_i>\mathbf{\alpha}_i \Rightarrow c<\lambda c < c$, yielding a contradiction. Therefore, there are no other positive eigenvectors except positive multiples of $\mathbf{\alpha}$. $\quad \square$

KL Divergence#

Definition

If $P$ and $Q$ are two probability distributions, then the Kullback-Leibler divergence from $Q$ to $P$ is defined as

$$D_{KL}(P||Q) = \sum_{x\in \mathcal{X}} P(x)\log\left(\frac{P(x)}{Q(x)}\right) = \mathbb{E}_{X \sim P}\left[\log\left(\frac{P(X)}{Q(X)}\right)\right]$$

$D_{KL}(P||Q)\neq D_{KL}(Q||P)$

Orbit-Stabilizer Theorem#

Let $G$ be a finite group acting on a finite set $X$. For any $x \in X$, let $O_x = \{g \cdot x \mid g \in G\}$ be the orbit of $x$ and $G_x = \{g \in G \mid g \cdot x = x\}$ be the stabilizer of $x$. Then $|G| = |O_x| \cdot |G_x|$

Proof

We construct a bijection between the orbit $O_x$ and the set of left cosets of the stabilizer $G/G_x$. Define a map $\phi: G/G_x \to O_x$ by $\phi(gG_x) = g \cdot x$.

1. Well-defined: If $g_1 G_x = g_2 G_x$, then $g_2^{-1}g_1 \in G_x$, so $g_2^{-1}g_1 \cdot x = x \implies g_1 \cdot x = g_2 \cdot x$. Thus $\phi$ is well-defined.
2. Injective: If $\phi(g_1 G_x) = \phi(g_2 G_x)$, then $g_1 \cdot x = g_2 \cdot x \implies g_2^{-1}g_1 \cdot x = x \implies g_2^{-1}g_1 \in G_x$, so $g_1 G_x = g_2 G_x$.
3. Surjective: For any $y \in O_x$, there exists $g \in G$ such that $y = g \cdot x$. Then $\phi(gG_x) = y$.

Since $\phi$ is a bijection, $\displaystyle |O_x| = [G : G_x] = \dfrac{|G|}{|G_x|}$. $\quad \square$

Cauchy’s Theorem#

If $G$ is a finite group and $p$ is a prime number such that $p \mid |G|$, then $G$ contains an element of order $p$.

Proof

Consider the set $S = \{(a_1, \dots, a_p) \in G^p \mid a_1 \dots a_p = e\}$. The first $p-1$ elements can be chosen arbitrarily, and $a_p$ is uniquely determined by $a_p = (a_1 \dots a_{p-1})^{-1}$. Thus $|S| = |G|^{p-1}$. Since $p \mid |G|$, we have $p \mid |S|$.

Let the cyclic group $\mathbb{Z}_p = \langle \sigma \rangle$ act on $S$ by cyclic shift: $\sigma \cdot (a_1, \dots, a_p) = (a_2, \dots, a_p, a_1)$. Note that if $a_1 \dots a_p = e$, then $a_1 (a_2 \dots a_p) = e \implies a_2 \dots a_p = a_1^{-1}$, so $a_2 \dots a_p a_1 = a_1^{-1} a_1 = e$. Thus the action is well-defined on $S$.

By the Orbit-Stabilizer Theorem, the size of any orbit divides $|\mathbb{Z}_p| = p$. So the orbit sizes can only be 1 or $p$. Let $k$ be the number of orbits of size 1. The elements in an orbit of size 1 satisfy $a_1 = \dots = a_p = a$ with $a^p = e$. Since $S$ is the disjoint union of orbits, we have

$$|S| = k \cdot 1 + m \cdot p \equiv k \pmod p$$

Since $p \mid |S|$, we must have $p \mid k$. Note that $(e, \dots, e) \in S$ forms an orbit of size 1, so $k \geq 1$. Since $p \mid k$, we must have $k \geq p \geq 2$. Thus there exists at least one non-identity element $a \in G$ such that $a^p = e$. $\quad \square$

Fundamental Theorem of Finite Abelian Groups#

Every finite abelian group $G$ is isomorphic to a direct sum of cyclic groups of prime power order. Moreover, the decomposition is unique up to reordering of the factors. $G \cong \mathbb{Z}_{p_1^{e_1}} \oplus \mathbb{Z}_{p_2^{e_2}} \oplus \cdots \oplus \mathbb{Z}_{p_k^{e_k}}$ where $p_i$ are primes (not necessarily distinct) and $e_i \ge 1$.

Alternatively, it can be stated as: Every finite abelian group $G$ is isomorphic to a direct sum of cyclic groups of orders $d_1, d_2, \dots, d_k$ such that $d_1 \mid d_2 \mid \dots \mid d_k > 1$. $G \cong \mathbb{Z}_{d_1} \oplus \mathbb{Z}_{d_2} \oplus \cdots \oplus \mathbb{Z}_{d_k}$ The integers $d_1, \dots, d_k$ are called the invariant factors of $G$.

Proof

The proof consists of two main steps: decomposing the group into its primary components (Sylow $p$-subgroups) and then decomposing each $p$-group into cyclic groups.

• Step 1: Primary Decomposition

  Let $|G| = n = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}$ be the prime factorization of the order of $G$. For each prime factor $p_i$, define the $p_i$-primary component (or Sylow $p_i$-subgroup) as: $G(p_i) = \{x \in G \mid |x| = p_i^{m} \text{ for some } m \ge 0\}$ Since $G$ is abelian, $G(p_i)$ is a subgroup of $G$. We claim that $G$ is the internal direct sum of these subgroups: $G \cong G(p_1) \oplus G(p_2) \oplus \dots \oplus G(p_k)$

  Proof of decomposition: Let $m_i = n / p_i^{e_i}$. Since $\gcd(m_1, \dots, m_k) = 1$, there exists integers $u_1, \dots, u_k$ such that $\sum_{i=1}^k u_i m_i = 1$. For any $x \in G$, we have $x = x^1 = x^{\sum u_i m_i} = \prod_{i=1}^k x^{u_i m_i}$. Let $x_i = x^{u_i m_i}$. Note that $(x_i)^{p_i^{e_i}} = x^{u_i m_i p_i^{e_i}} = x^{u_i n} = (x^n)^{u_i} = e^{u_i} = e$. Thus $|x_i|$ divides $p_i^{e_i}$, so $x_i \in G(p_i)$. So $G = G(p_1) \dots G(p_k)$. To show the sum is direct, suppose $x_1 \dots x_k = e$ with $x_i \in G(p_i)$. Fix $j$. Since $|x_i|$ is a power of $p_i$, the order of $y = \prod_{i \ne j} x_i = x_j^{-1}$ divides $\prod_{i \ne j} |x_i|$, which is coprime to $p_j$. But $y = x_j^{-1} \in G(p_j)$ has order a power of $p_j$. The only element with order dividing two coprime numbers is the identity. Thus $x_j = e$.

  Thus, it suffices to prove the theorem for finite abelian $p$-groups.

• Step 2: Structure of Finite Abelian $p$-groups

  Let $G$ be a finite abelian $p$-group. We proceed by induction on $|G|$. Let $a \in G$ be an element of maximal order. Let $H = \langle a \rangle$. We claim that $H$ is a direct summand of $G$, i.e., there exists a subgroup $K$ such that $G = H \oplus K$. Consider the quotient group $G / H$. By induction, $G / H$ is a direct sum of cyclic groups. By lifting the generators of these cyclic groups back to $G$ and adjusting them using the maximality of the order of $a$, one can construct the subgroup $K$. Since $|K| < |G|$, by the induction hypothesis, $K$ is a direct sum of cyclic groups. Therefore, $G = H \oplus K$ is a direct sum of cyclic groups.

Combining these steps, any finite abelian group decomposes into a direct sum of cyclic $p$-groups. Grouping these appropriately yields the invariant factor decomposition. $\quad \square$