You are currently browsing the tag archive for the ‘gauss’ tag.

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

Definition 1 Let ${M}$ be an ${n\times n}$ matrix written as a ${2\times2}$ block matrix

$\displaystyle M=\left[\begin{array}{cc} A & B\\ C & D \end{array}\right],$

where ${A}$ is a ${p\times p}$ matrix, ${D}$ is a ${q\times q}$ matrix, ${B}$ is a ${p\times q}$, and ${C}$ is a ${q\times p}$, so ${n=p+q}$. Assuming ${A}$ is nonsingular, then

$\displaystyle M/A=D-CA^{-1}B$

is called the Schur complement of ${A}$ in ${M}$; or the Schur complement of ${M}$ relative to ${A}$.

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

$\displaystyle \left[\begin{array}{cc} A & B\\ C & D \end{array}\right]\left[\begin{array}{c} x\\ y \end{array}\right]=\left[\begin{array}{c} c\\ d \end{array}\right],$

that is

$\displaystyle \begin{array}{rcl} Ax+By & = & c\\ Cx+Dy & = & d, \end{array}$

by mimicking Gaussian elimination, that is, if ${A}$ is square and nonsingular, then by eliminating ${x}$, by multiplying the first equation by ${CA^{-1}}$ and subtracting the second equation, we get

$\displaystyle (D-CA^{-1}B)y=d-CA^{-1}c.$

Note, the matrix ${D-CA^{-1}B}$ is the Schur complement of ${A}$ in ${M}$, 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

$\displaystyle M=\left[\begin{array}{cc} A & B\\ C & D \end{array}\right],$

where ${A}$ is square and nonsingular. We can change ${M}$ so that the lower-left and upper-right submatrices become ${0}$. More precisely, we can make the lower-left and upper-right submatrices ${0}$ by subtracting the first row multiplied by ${CA^{-1}}$ from the second row, and by subtracting the first column multiplied by ${A^{-1}B}$ from the second column. In symbols,

$\displaystyle \left[\begin{array}{cc} A & B\\ C & D \end{array}\right]\rightarrow\left[\begin{array}{cc} A & B\\ 0 & D-CA^{-1}B \end{array}\right]\rightarrow\left[\begin{array}{cc} A & 0\\ 0 & D-CA^{-1}B \end{array}\right],$

and in equation form,

$\displaystyle \left[\begin{array}{cc} I & 0\\ -CA^{-1} & I \end{array}\right]\left[\begin{array}{cc} A & B\\ C & D \end{array}\right]\left[\begin{array}{cc} I & -A^{-1}B\\ 0 & I \end{array}\right]=\left[\begin{array}{cc} A & 0\\ 0 & D-CA^{-1}B \end{array}\right].$

Note that we have obtain the following factorization of ${M}$:

$\displaystyle \left[\begin{array}{cc} A & B\\ C & D \end{array}\right]=\left[\begin{array}{cc} I & 0\\ CA^{-1} & I \end{array}\right]\left[\begin{array}{cc} A & 0\\ 0 & D-CA^{-1}B \end{array}\right]\left[\begin{array}{cc} I & A^{-1}B\\ 0 & I \end{array}\right].$

By taking the determinants

$\displaystyle \left|\begin{array}{cc} A & B\\ C & D \end{array}\right|=\left|\begin{array}{cc} I & 0\\ CA^{-1} & I \end{array}\right|\left|\begin{array}{cc} A & 0\\ 0 & D-CA^{-1}B \end{array}\right|\left|\begin{array}{cc} I & A^{-1}B\\ 0 & I \end{array}\right|.$

we obtain the Schur’s determinant formula for ${2\times2}$ block matrices,

$\displaystyle \det M=\det A\;\det(M/A).$

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 ${2\times2}$ block matrix proof, focusing on ${m\times n}$ complex matrices.

Proof: Let ${A,B\in\mathbb{C}^{m\times n}}$. Then

$\displaystyle M=\left[\begin{array}{cc} I & A^{*}\\ B & I \end{array}\right]\left[\begin{array}{cc} I & B^{*}\\ A & I \end{array}\right]=\left[\begin{array}{cc} I+A^{*}A & A^{*}+B^{*}\\ A+B & I+BB^{*} \end{array}\right]\geq0.$

By taking the Schur complement of ${I+A^{*}A}$, we arrive at

$\displaystyle S=I+BB^{*}-(A+B)(I+A^{*}A)^{-1}(A^{*}+B{}^{*})\geq0$

and hence

$\displaystyle (I+A^{*}A)(I+BB^{*})\geq(A+B)(A+B)^{*}.$

which ensures, when ${A}$ and ${B}$ are square, that

$\displaystyle \left|\det(A+B)\right|^{2}\leq\det(I+A^{*}A)\;\det(I+BB^{*}).$

Equality occurs if and only if rank ${M=}$ rank ${A}$; that is, by the Guttman rank additivity formula, rank ${M=}$ rank ${A+}$rank ${S}$ if and only if ${S=0}$. When ${A}$ is nonsingular, ${M}$ is nonsingular if and only if ${S}$ is nonsingular.$\Box$

References

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

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

$\displaystyle F_{n}=2^{2^{n}}+1,$

so that ${F_{0}=3,F_{1}=5,F_{2}=17,F_{3}=257,}$ and ${F_{4}=65537}$. They are of great interest in many ways: for example, it was proved by Gauss that, if ${F_{n}}$, is a prime ${p}$, then a regular polygon of ${p}$ 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

$\displaystyle F_{5}=2^{2^{5}}+1=641\cdot6700417$

is composite.

In 1880 Landry proved that

$\displaystyle F_{6}=2^{2^{6}}+1=274177\cdot67280421310721.$

It is currently known that ${F_{n}}$, is composite for ${5 \leq n \leq 32}$. Factoring Fermat numbers is extremely difficult as a result of their large size. ${F_{12}}$ has ${5}$ known factors with ${C1187}$ remaining (where ${C}$ denotes a composite number with $n$ digits). ${F_{13}}$ has ${4}$ known factors with ${C2391}$ remaining. ${F_{14}}$ 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: ${F_{14},F_{20},F_{22},}$ and ${F_{14}}$. In all the other cases proved to be composite a factor is known. No prime ${F_{n}}$ has been found beyond ${F_{4}}$, 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 ${F_{n}=2^{2^{n}}+1}$ for ${n=0,1,2,\cdots}$. 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

$\displaystyle \prod_{k=0}^{n-1}F_{k}=F_{n}-2\quad(n\geq1),$

from which our assertion follows immediately. Indeed, if ${m}$ is a divisor of, say, ${F_{k}}$ and ${F_{n}}$ ${(k, then ${m}$ divides ${2}$, and hence ${m=1}$ or ${2}$. But ${m=2}$ is impossible since all Fermat numbers are odd.

To prove the recursion we use induction on ${n}$. For ${n=1}$ we have ${F_{0}=3}$ and ${F_{1}-2=5-2=3}$. With induction we now conclude

$\displaystyle \begin{array}{rcl} \prod_{k=0}^{n} F_{k} & = & \left(\prod_{k=0}^{n-1}F_{k}\right)F_{n}\\ & = & (F_{n}-2)F_{n}\\ & = & (2^{2^{n}}-1)(2^{2^{n}}+1)\\ & = & 2^{2^{n+1}}-1\\ & = & F_{n+1}-2. \Box \end{array}$

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.

Euler Formula

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

$\displaystyle e^{ix}=cosx+isinx,$

where ${i}$ 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 ${x=\pi}$ gives the beautiful identity

$\displaystyle e^{i\pi}=-1,$

an equation connecting the fundamental numbers ${i,\pi,e,1,}$ and ${0}$, the fundamental operations ${+}$, ${\times}$, 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.