You are currently browsing the category archive for the ‘Elementary’ category.

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 $*$ denote 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$ denote the usual inner product of two vectors $x,y$, i.e.,

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

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.

This is elementary, yet useful and interesting.

Statement: All eigenvalues of a Hermitian matrix are real.

Proof: