The Rank Lemma

The following result gives a lower bound for the rank of a square matrix in terms of its trace and Frobenius norm (a.k.a. Hilbert-Schmidt norm).

Lemma 1 Let ${A=[a_{i,j}]}$ be any ${n\times n}$ matrix with complex entries. Then

$\displaystyle \left|\sum_{i=1}^n a_{i,i}\right|^2\leq \mathop{\mathrm{rank}} (A)\biggl(\sum_{i=1}^n\sum_{j=1}^n|a_{i,j}|^2\biggr). \ \ \ \ \ (1)$

Equality holds in (1) if and only if ${A}$ is a normal matrix and all its non-zero eigenvalues are equal. If ${A}$ is a real matrix then equality holds in (1) if and only if ${A}$ is symmetric and all its non-zero eigenvalues are equal.

The special case where ${A}$ is real and symmetric is an exercise on p.~137 of Bellman’s of a square matrix, and looking at Schur’s original 1909 paper gives the impression that Schur could have known this.

Various combinatorial and geometric applications have been given by Noga Alon and others (see my paper for more references). These papers all use (1) only for symmetric matrices. If ${A}$ is not symmetric, the following argument implies a weakening of (1) by a factor of ${2}$ .

Apply (1) to the symmetric matrix ${A+A^T}$ , which has rank at most ${2\mathop{\mathrm{rank}}(A)}$ , to obtain

$\displaystyle \frac{\left|\sum_i a_{i,i}\right|^2}{\sum_{i,j}|a_{i,j}|^2} \leq \frac{\left|\sum_i 2a_{i,i}\right|^2}{\sum_{i,j}|a_{i,j}+a_{j,i}|^2} \leq 2\mathop{\mathrm{rank}}(A),$

where the first inequality follows from the Cauchy-Schwarz inequality in the form ${\sum_{i,j}a_{i,j}\overline{a_{j,i}}\leq\sum_{i,j}|a_{i,j}|^2}$ .

This weakening is usually of no concern in applications. However, in this paper of mine I needed the sharp estimate (1) for general non-symmetric (although real) matrices.

Before giving a proof of Lemma 1, I present the following application, which is a slight strengthening of Lemma 2 of this post by Terence Tao.

Lemma 2 Let ${0<c<1}$ . Let ${v_1,\dots,v_m}$ be unit vectors in ${{\mathbb R}^n}$ such that ${|\langle v_i,v_i\rangle|\leq c/\sqrt{n^{1/2}}}$ for all distinct ${i,j}$ . Then ${m<n/(1-c^2)}$ .

In particular, if ${|\langle v_i,v_i\rangle\leq 1/\sqrt{2n^{1/2}}}$ for all distinct ${i,j}$ , then ${m<2n}$ .

Proof: Consider the Gram matrix ${A=[a_{i,j}]_{i,j}:=[\langle v_i,v_j\rangle]_{i,j}}$ of ${\{v_1,v_2,\dots,v_m\}}$ . Its rank is ${\leq n}$ , its trace is ${\sum_{i=1}^n a_{i,i}=m}$ , and the square of its Frobenius norm satisfies ${\sum_{i=1}^n\sum_{j=1}^n a_{i,j}^2 \leq m + \frac{m(m-1)c^2}{n}}$ . Substitute back into (1) and solve for ${m}$ to obtain

$\displaystyle m \leq\frac{n-c^2}{1-c^2}.$ $\Box$

We end with the proof of Lemma 1.

Proof: Let the non-zero eigenvalues of ${A}$ be ${\lambda_1,\dots,\lambda_r}$ . Since the result is trivial if ${\mathop{\mathrm{tr}}(A)=\sum_{i=1}^n a_{i,i} =0}$ , we may assume without loss of generality that ${r\geq 1}$ . By the Schur decomposition of a square matrix with complex entries there exists an ${n\times n}$ unitary matrix ${U}$ such that ${C=[c_{i,j}]:=U^\ast A U}$ is upper triangular. In particular, the eigenvalues of ${A}$ are the diagonal entries of ${C}$ , and

$\displaystyle r\leq\mathop{\mathrm{rank}}{C}=\mathop{\mathrm{rank}}{A}. \ \ \ \ \ (2)$

Also,

$\displaystyle \left|\sum_{i=1}^n a_{i,i}\right| =|\mathop{\mathrm{tr}}(A)| =\left|\sum_{i=1}^r\lambda_i\right|\leq\sum_{i=1}^r|\lambda_i|, \ \ \ \ \ (3)$

and

$\displaystyle \sum_{i=1}^n\sum_{j=1}^n|a_{i,j}|^2=\mathop{\mathrm{tr}}(A^\ast A)=\mathop{\mathrm{tr}}(C^\ast C)=\sum_{i=1}^n\sum_{j=1}^n|c_{i,j}|^2\geq\sum_{i=1}^r|\lambda_i|^2. \ \ \ \ \ (4)$

(This inequality ${\sum_{i}|\lambda_i|^2\leq\sum_{i,j}|a_{i,j}|^2}$ is in Schur’s 1909 paper.) Finally, by the Cauchy-Schwarz inequality,

$\displaystyle \Bigl(\sum_{i=1}^r|\lambda_i|\Bigr)^2\leq r\sum_{i=1}^r|\lambda_i|^2, \ \ \ \ \ (5)$

and (1) follows from (2), (3), (4) and (5).

Suppose that equality holds in (1). This gives equality in (2)—(5). Equality in (5) gives that all ${|\lambda_i|}$ are equal. Equality in (3) implies that all ${\lambda_i}$ are positive multiples of each other. Therefore, all ${\lambda_i}$ are equal. Equality in (4) gives that ${C}$ is a diagonal matrix, hence ${A}$ is normal. If ${A}$ is real we furthermore obtain that the ${\lambda_i}$ are real, since they are equal and their sum is the real number ${\mathop{\mathrm{tr}}(A)}$ . Then ${C=C^\ast}$ , hence ${A^T=A^\ast=A}$ and ${A}$ is symmetric.

Conversely, if ${A}$ is normal, then ${C}$ is diagonal, and equality holds in (2) and (4). If all the non-zero eigenvalues of ${A}$ are equal, equality holds in (3) and (5), and we obtain equality in (1). $\Box$

Geometry and Combinatorics

Konrad Swanepoel's blog

The Rank Lemma

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply