Volume and Hadamard's Inequality

体积与阿达马不等式 苏剑林 · 2013-12-26 · Mathematics inequality geometry matrix determinant

Volume and the Hadamard Inequality

Hadamard's Inequality

Let $\boldsymbol{A}=(a_{ij})_{n\times n}$ be a real matrix of order $n$. Then its determinant satisfies the Hadamard inequality

$$\begin{equation} \left(\det \boldsymbol{A}\right)^2 \leq \prod\limits_{i=1}^{n}\left(a_{1i}^2+a_{2i}^2+\dots+a_{ni}^2\right) \end{equation}$$

This was first published by Hadamard in 1893. If we think of the determinant as a volume, the inequality above has a fairly obvious geometric meaning. When $n=2$, it simply says that the area of a parallelogram cannot exceed the product of the lengths of its two sides; when $n=3$, it says that the volume of a parallelepiped cannot exceed the product of the lengths of its three edges; and this generalizes naturally to higher dimensions. In geometry, these facts are almost "obviously true." So it's hard to understand why this inequality wasn't discovered until 1893. Of course, algebra won't accept such a loose argument — it demands a rigorous proof. more

However, whether in textbook hints or in materials I found online (such as the paper attached to this post), the proofs are almost invariably based on the theory of positive-definite matrices. But for an inequality whose geometric meaning is so obvious and so basic, having to lay the groundwork of positive-definite matrix theory just to prove it feels like putting the cart before the horse. This also reflects a common bad habit among many domestic mathematics practitioners: a lack of independent mathematical thinking, and a tendency to simply follow the crowd. (Once the first person did it this way, a large number of people followed suit — and even when the method varies slightly, it never really departs from the original approach.) In fact, there's no need for positive-definite matrices at all; the inequality can be proved by a purely geometric method.

The Best Coordinate System

Think of a matrix as a collection of $n$ column vectors $\boldsymbol{a}_1,\boldsymbol{a}_2,\dots,\boldsymbol{a}_n$:

$$\begin{equation} \boldsymbol{A}=[\boldsymbol{a}_1,\boldsymbol{a}_2,\dots,\boldsymbol{a}_n] \end{equation}$$

To find the volume of the parallel $n$-dimensional body formed by these $n$ column vectors, we need to rotate the original coordinate system slightly — that is, switch to a different rectangular coordinate system in which these $n$ vectors take the simplest possible form. In algebraic terms, this means finding an orthogonal matrix $\boldsymbol{U}$ such that $\boldsymbol{A}=\boldsymbol{U}\boldsymbol{T}$, with $\boldsymbol{T}$ having as simple a form as possible (so that its determinant is easy to compute).

What coordinate system is optimal? Let $\boldsymbol{e}_1,\boldsymbol{e}_2,\dots,\boldsymbol{e}_n$ be the basis of the new coordinate system; naturally, these are also pairwise orthogonal unit vectors. (Only this way is the volume preserved — algebraically speaking, orthogonal transformations preserve determinants.) It is natural to choose one of these vectors, say $\boldsymbol{e}_1=\frac{\boldsymbol{a}_1}{|\boldsymbol{a}_1|}$, to lie along one coordinate axis, so that $\boldsymbol{a}_1$ has the simplest possible expression. To make the expression for $\boldsymbol{a}_2$ as simple as possible, we should let $\boldsymbol{a}_2$ lie in a coordinate plane; constructively, this means building a vector from $\boldsymbol{e}_1$ and $\boldsymbol{a}_2$ so that it becomes the $\boldsymbol{e}_2$ axis, making $\boldsymbol{a}_2$ a linear combination of $\boldsymbol{e}_1$ and $\boldsymbol{e}_2$. Likewise, to make the expression for $\boldsymbol{a}_3$ as simple as possible, $\boldsymbol{a}_3$ should be expressible as a linear combination of $\boldsymbol{e}_1,\boldsymbol{e}_2,\boldsymbol{e}_3$, which is equivalent to constructing $\boldsymbol{e}_3$ from $\boldsymbol{a}_1,\boldsymbol{a}_2,\boldsymbol{a}_3$. Carrying this process on to the end, we see that it is precisely the Gram–Schmidt orthonormalization process applied to the vectors $\{\boldsymbol{a}_1,\boldsymbol{a}_2,\dots,\boldsymbol{a}_n\}$!

In other words, the vector set $\boldsymbol{e}_1,\boldsymbol{e}_2,\dots,\boldsymbol{e}_n$ obtained by orthonormalizing $\boldsymbol{a}_1,\boldsymbol{a}_2,\dots,\boldsymbol{a}_n$ gives one of the best rectangular coordinate systems for representing the original vectors. This vector set forms an orthogonal matrix $\boldsymbol{U}$:

$$\begin{equation} \boldsymbol{U}=[\boldsymbol{e}_1,\boldsymbol{e}_2,\dots,\boldsymbol{e}_n] \end{equation}$$

In this coordinate system, we have

$$\begin{equation} \boldsymbol{A}=[\boldsymbol{a}_1,\boldsymbol{a}_2,\dots,\boldsymbol{a}_n]=[\boldsymbol{e}_1,\boldsymbol{e}_2,\dots,\boldsymbol{e}_n]\boldsymbol{T}=\boldsymbol{U}\boldsymbol{T} \end{equation}$$

where

$$\begin{equation} \boldsymbol{T}=\left[ {\begin{array}{\cdot {20}{c}} {\lambda_1}&{\cdot }&{\dots}&{\cdot }\\ {}&{\lambda_2}&{\dots}&{\cdot }\\ {}&{}&{\ddots}&{\vdots}\\ {0}&{}&{}&{\lambda_n} \end{array}} \right] \end{equation}$$

is an upper triangular matrix.

Completing the Proof

With the result above, the proof of the Hadamard inequality becomes very simple. Since $\boldsymbol{U}$ is an orthogonal matrix, we naturally have

$$\begin{equation} \begin{array}{l} \left| {\boldsymbol{a}_1} \right| = \left| {\left( \lambda_1 \right)} \right|\geq \lambda_1,\left| {\boldsymbol{a}_2} \right| = \left| {\left( {\begin{array}{\cdot {20}{c}} \cdot \\ \lambda_2 \end{array}} \right)} \right|\geq \lambda_2\\ \dots \\ \left| {\boldsymbol{a}_n} \right| = \left| {\left( {\begin{array}{\cdot {20}{c}} \begin{array}{l} \cdot \\ \cdot \\ \vdots \end{array}\\ \lambda_n \end{array}} \right)} \right|\geq \lambda_n \end{array} \end{equation}$$

and therefore

$$\begin{equation} \begin{aligned} (\det\boldsymbol{A})^2&=(\det\boldsymbol{T})^2=(\lambda_1 \lambda_2 \dots\lambda_n)^2\\ &\leq |\boldsymbol{a}_1|^2 |\boldsymbol{a}_2|^2 \dots |\boldsymbol{a}_n|^2\\ &=\prod\limits_{i=1}^{n}\left(a_{1i}^2+a_{2i}^2+\dots+a_{ni}^2\right) \end{aligned} \end{equation}$$

This completes the proof of the Hadamard inequality — a geometric proof!

Closing Remarks

When studying linear algebra, and especially the theory of matrices, it is extremely useful and indeed necessary to hold firmly onto the geometric meaning behind it — I have felt this deeply myself. Whether from the standpoint of memory or of reasoning, geometry gives us the most intuitive way of thinking, so that we never have to accept a concept with absolutely no sense of what it means. It cannot be overstated: rote memorization is useless in mathematics.

Attachment:

Proof and Geometric Meaning of the Hadamard Inequality