The Rank Lemma

Posted on by | Leave a comment

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

Journal of Computational Geometry

Posted on by | Leave a comment

What does it cost to run an open access journal? The Journal of Computational Geometry recently released their financial statements of the past three years.

http://jocg.org/index.php/jocg/announcement

Of course there’s a lot of freely donated labour that’s makes this possible, but non-free journals get similar donations.

3 X 3 Reuleaux triangles

Posted on by | Leave a comment

Update 25th September 2009: for a very similar picture, see this post by David Eppstein.

[The piece below used to lie around on my homepage since April 2007. I’m slowly closing down that site, as the party is over at Google’s Page Creator.]

lawlormorgan1-old

The picture above is something that came out of my work with Achill Schürmann. It is used to disprove a conjecture of Gary Lawlor and Frank Morgan. Continue reading →

Some musings around Borsuk’s conjecture

Posted on by | 2 Comments

Borsuk conjectured in 1933 that any bounded subset of n-dimensional Euclidean space can be partitioned into n+1 parts, all of smaller diameter. An equilateral simplex shows that that you need at least n+1 parts. The famous Borsuk-Ulam theorem can be formulated as saying that you also need at least n+1 parts for the Euclidean (n-1)-sphere. (Note that n+1 parts also suffice for the sphere.)

Borsuk’s conjecture is true in dimensions 2 and 3. In 1993 Kahn and Kalai proved that the conjecture is false if the dimension is sufficiently large. For a short explanation by Gil Kalai, click here. For a wonderful (very) short story on how their proof came about, click here. The lowest dimension for which it is currently known that the conjecture fails is n=298, due to Aicke Hinrichs and Christian Richter.

It is not so difficult to prove the 2-dimensional case. The 3-dimensional case, first proved by Eggleston, is somewhat messy. A short proof for finite sets in 3-space was found by Heppes and Revesz (1956). It goes as follows.

The number of diameter pairs in a set S of n points in 3-space is at most 2n-2. (A diameter pair of S is a pair of points in S whose distance equals the diameter of S.)

Therefore, the diameter graph of S has average degree at most 4-4/n. So we can always find a point incident to at most 3 diameters of S.

So we can greedily 4-colour the graph.

The colour classes give the partition!

Problem: Can this argument be modified easily to also work for infinite sets? For example, a solution to the following problem would imply Eggleston’s theorem:

Show that there exist \varepsilon>0 such that the graph G of almost-diameter pairs on any finite set S has chromatic number at most 4.

Here we define G of almost-diameter pairs to be the graph on S with edges all pairs of points at distance at least 1-\varepsilon times the diameter of S.

In general, it is not clear how to go from finite sets to general bounded sets. So it is “conceivable” for example that the conjecture holds for all finite sets in 4-dimensional space, but not for all bounded sets….

LaTeX hints

Posted on by | Leave a comment

I guess this is off-topic, but I’m always forgetting how to do stuff in \LaTeX. Here are two useful things:

Braces with labels

Do this:

$\ell_p^d=\overbrace{\ell_p^k\oplus\dots\oplus\ell_p^k}^{m \text{ times}}\oplus\ell_p^r$

to get this:

\ell_p^d=\overbrace{\ell_p^k\oplus\dots\oplus\ell_p^k}^{m \text{ times}}\oplus\ell_p^r

With the obvious variation

$\ell_p^d=\underbrace{\ell_p^k\oplus\dots\oplus\ell_p^k}_{m \text{ times}}\oplus\ell_p^r$

to get this:

\ell_p^d=\underbrace{\ell_p^k\oplus\dots\oplus\ell_p^k}_{m \text{ times}}\oplus\ell_p^r

Breaking “n-dimensional”

In order to convince \LaTeX to break n-dimensional correctly, use

$n$\nobreakdash-\hspace{0pt}dimensional

(Otherwise \LaTeX will not do anything).

Latex blogs

For more serious stuff, see the Blog on Latex Matters or the Blog on Latex Matters (yes, you’re seeing double). The WordPress FAQ is also useful for latexblogging.