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.

Continue reading “The Structure of a Quotient Ring modulo x^p-1”

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 x,y \rangle := y^*x denotes the usual inner product of two vectors x,y.

Continue reading “In a Hermitian Matrix, the Eigenvectors of Different Eigenvalues are Orthogonal”

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.

 

Continue reading “Upper Bounds on Binomial Coefficients using Stirling’s Approximation”