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.

Read the rest of this entry »

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 kth 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:

Read the rest of this entry »