# The Structure of a Quotient Ring modulo x^p-1

Let $f(X)=X^p-1 \in F_l[X]$ for a prime $p$. We are interested in the structure of the ring $R=F_l[X]/(f)$. Via the Chinese Remainder Theorem, this question is equivalent to finding a factorization of $f$ over $F_l$. Suppose $f$ factors in $F_l$ as

$\displaystyle f(X) = (X-1) \prod_i^s{q_i(X)} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (*)$

where each $q_i$ is an irreducible polynomial. What are the degrees of $q_1, \cdots, q_s$? What is $s$?

We claim that $R=F_l \oplus (F_{l^r})^s,$ where $r$ is the multiplicative order of $l$ mod $p$.

This structure has been used in a beautifully instructive paper by Evra, Kowalski, and Lubotzky. (Yes, the one in Lubotzky-Philip-Sarnak.) In this paper, they have established connections among the Fourier transform, uncertainty principle, and dimension of ideals generated by polynomials in the ring $R$ above. We’ll talk about these connections in another post. The content of this post is Proposition 2.6(3) from their paper.

Advertisements

# In a Hermitian Matrix, the Eigenvectors of Different Eigenvalues are Orthogonal

This is an elementary (yet important) fact in matrix analysis.

Statement

Let $M$ be an $n\times n$ complex Hermitian matrix which means $M=M^*$ where $*$ denotes the conjugate transpose operation. Let $\lambda_1, \neq \lambda_2$ be two different  eigenvalues of $M$. Let $x, y$ be the two eigenvectors of $M$ corresponding to the two eigenvalues $\lambda_1$ and $\lambda_2$, respectively.

Then the following is true:

$\boxed{\lambda_1 \neq \lambda_2 \iff \langle x, y \rangle = 0.}$

Here $\langle a,b\rangle$ denotes the usual inner product of two vectors $x,y$, i.e.,

$\langle x,y \rangle := y^*x$.

# Upper Bounds on Binomial Coefficients using Stirling’s Approximation

We need to bound the binomial coefficients a lot of times. In this post, we will prove bounds on the coefficients of the form ${n \choose k}, {n \choose \alpha n}$ and ${(1-\alpha)n \choose \alpha n}$ where $\alpha \in (0, 1/2]$ and $\alpha n$ is an integer.

Proposition 1. For positive integers $n, k$ such that $1 \leq k \leq n$,

$\displaystyle {n \choose k} \leq \left( \frac{n e}{k} \right)^k.$

Proposition 2. For a positive integer $n$ and any $\alpha$ such that $\alpha n \in \mathbb{N}$ and $\displaystyle \frac{1}{n} \leq \alpha \leq \frac{1}{2}$,

$\displaystyle {n \choose \alpha n} \leq 2^{n H(\alpha)}$

where the binary entropy function $H : [0, 1] \rightarrow [0, 1]$ is defined as follows:

$\displaystyle H(\alpha) := \left\{ \begin{array}{ll}0\,, & \text{ if } \alpha \in \{0, 1\}\\ -\alpha \log_2(\alpha) - (1-\alpha) \log_2(1-\alpha)\, , & \text{ if } \alpha \in (0, 1) \end{array} \right.$

Proposition 3. For a positive integer $n$ and any $\alpha$ such that $\alpha n \in \mathbb{N}$ and $\displaystyle 1 \leq n\alpha \leq \left\lfloor n\left( \frac{1}{2} - \frac{1}{2n} \right) \right\rfloor$ ,

$\displaystyle {(1-\alpha)n \choose \alpha n} \leq \frac{2^{(1-\alpha)n\,H\left( \frac{\alpha}{1-\alpha} \right)} }{ \sqrt{(1-2\alpha) n}} \leq 2^{(1-\alpha)n\,H\left( \frac{\alpha}{1-\alpha} \right)}$

where $H(.)$ is the binary entropy function.

# Eigenvalues of a Hermitian Matrix are Real

This is elementary, yet useful and interesting.

Statement: All eigenvalues of a Hermitian matrix are real.

Proof: