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

# 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 bounding n choose k

We want to show that for $1\leq k\leq n$, the following holds: ${n\choose k} \leq \Big(\frac{n\cdot e}{k}\Big)^k.$

First, recall the power series $e^k=\sum_{i=0}^\infty{\frac{k^i}{i!}}$. For $k \geq 1$, this sum is definitely larger than its $k$th term only. In other words, $e^k \geq k^k/k!$, which implies $k! \geq (k/e)^k$. Now,

$\begin{matrix}{n\choose k} &=& \frac{n!}{k! \cdot (n-k)!}\\ &=& \frac{n(n-1)(n-2)\cdots (n-(k-1))}{k!}\\ &\leq& \frac{n^k}{k!} \\ &\leq& \frac{n^k}{(k/e)^k} \\ &=& (\frac{en}{k})^k.\\ \end{matrix}$

This proof is extracted from the StackExchange discussion here. For more inequalities/bounds for binomial coefficients, see Wikipedia.

# Eigenvalues of a Hermitian Matrix are Real

This is elementary, yet useful and interesting.

Statement: All eigenvalues of a Hermitian matrix are real.

Proof: