The Cauchy-Schwarz Inequality 2: The Schur Complement

In the previous post, two proofs were given for the Cauchy-Schwarz inequality. We will now consider another proof.

Definition 1 Let be an matrix written as a block matrix

where is a matrix, is a matrix, is a , and is a , so . Assuming is nonsingular, then

is called the Schur complement of in ; or the Schur complement of relative to .

The Schur complement probably goes back to Carl Friedrich Gauss (1777-1855) (for Gaussian elimination). To solve the linear system

that is

by mimicking Gaussian elimination, that is, if is square and nonsingular, then by eliminating , by multiplying the first equation by and subtracting the second equation, we get

Note, the matrix is the Schur complement of in , and if it is square and nonsingular, then we can obtain the solution to our system.

The Schur complement comes up in Issai Schur’s (1875-1941) seminal lemma published in 1917, in which the Schur determinate formula was introduced. By considering elementary operations of partitioned matrices, let

where is square and nonsingular. We can change so that the lower-left and upper-right submatrices become . More precisely, we can make the lower-left and upper-right submatrices by subtracting the first row multiplied by from the second row, and by subtracting the first column multiplied by from the second column. In symbols,

and in equation form,

Note that we have obtain the following factorization of :

By taking the determinants

we obtain the Schur’s determinant formula for block matrices,

Mathematician Emilie Virginia Haynsworth (1916-1985) introduced a name and a notation for the Schur complement of a square nonsingular (or invertible) submatrix in a partitioned (two-way block) matrix. The term Schur complement first appeared in Emily’s 1968 paper On the Schur Complement in Basel Mathematical Notes, then in Linear Algebra and its Applications Vol. 1 (1968), AMS Proceedings (1969), and in Linear Algebra and its Applications Vol. 3 (1970).

We will now present a block matrix proof, focusing on complex matrices.

Proof: Let . Then

By taking the Schur complement of , we arrive at

and hence

which ensures, when and are square, that

Equality occurs if and only if rank rank ; that is, by the Guttman rank additivity formula, rank rank rank if and only if . When is nonsingular, is nonsingular if and only if is nonsingular.

References

[1] Zhang, Fuzhen. Matrix theory: basic results and techniques. Springer Science & Business Media, 2011.

Advertisements

Fermat Numbers

Proofs from THE BOOK by Martin Aigner and Günter Ziegler begins by giving six proofs of the infinity of primes. We will go over the third proof. Before we go over this proof, lets cover some background.

— 1. Fermat Numbers —

Fermat numbers are defined by

so that and . They are of great interest in many ways: for example, it was proved by Gauss that, if , is a prime , then a regular polygon of sides can be inscribed in a circle by Euclidean methods. The property of the Fermat numbers which is relevant here is

Theorem 1 No two Fermat numbers have a common divisor greater than 1.

We will prove this theorem later.

The first four Fermat numbers are prime, and Fermat conjectured that all were prime. Euler, however, found in 1732 that

is composite.

In 1880 Landry proved that

It is currently known that , is composite for . Factoring Fermat numbers is extremely difficult as a result of their large size. has known factors with remaining (where denotes a composite number with digits). has known factors with remaining. has no known factors but is composite. There are currently four Fermat numbers that are known to be composite, but for which no single factor is known: and . In all the other cases proved to be composite a factor is known. No prime has been found beyond , and it seems unlikely that any more will be found using current computational methods and hardware.

— 2. Infinitude of Primes Theorem —

We are now ready to prove Euclid’s Second Theorem, also called the Infinitude of Primes Theorem using the third proof in Proofs from THE BOOK.

Theorem 2 (Euclid’s Second Theorem) The number of primes is infinite.

Proof: Next let us look at the Fermat numbers for . We will show that any two Fermat numbers are relatively prime (Theorem 1); hence there must be infinitely many primes. To this end, we verify the recursion

from which our assertion follows immediately. Indeed, if is a divisor of, say, and , then divides , and hence or . But is impossible since all Fermat numbers are odd.

To prove the recursion we use induction on . For we have and . With induction we now conclude

Nonplanar Gauss codes

IMAGE: This knot has Gauss code O1U2O3U1O2U3.

In his article “The Combinatorial Revolution in Knot Theory”, to appear in the December 2011 issue of the Notices of the AMS, Sam Nelson describes a novel approach to knot theory that has gained currency in the past several years and the mysterious new knot-like objects discovered in the process.

As Nelson reports in his article, mathematicians have devised various ways to represent the information contained in knot diagrams. One example is the Gauss code, which is a sequence of letters and numbers wherein each crossing in the knot is assigned a number and the letter O or U, depending on whether the crossing goes over or under. The Gauss code for a simple knot might look like this: O1U2O3U1O2U3.

In the mid-1990s, mathematicians discovered something strange. There are Gauss codes for which it is impossible to draw planar knot diagrams but which nevertheless behave like knots in certain ways. In particular, those codes, which Nelson calls *nonplanar Gauss codes*, work perfectly well in certain formulas that are used to investigate properties of knots. Nelson writes: “A planar Gauss code always describes a [knot] in three-space; what kind of thing could a nonplanar Gauss code be describing?” As it turns out, there are “virtual knots” that have legitimate Gauss codes but do not correspond to knots in three-dimensional space. These virtual knots can be investigated by applying combinatorial techniques to knot diagrams. Read the article here.

e to the pi times i

Euler Formula

The Euler formula, sometimes also called the Euler identity, states

where is the imaginary unit. Note that Euler’s polyhedral formula is sometimes also called the Euler formula, as is the Euler curvature formula.

The special case of the formula with gives the beautiful identity

an equation connecting the fundamental numbers and , the fundamental operations , , and exponentiation, the most important relation , and nothing else. Gauss is reported to have commented that if this formula was not immediately obvious, the reader would never be a first-class mathematician.