Hadamard’s inequality via Lagrange multiplier

lagrange multiplierlinear algebraoptimizationpartial derivativereal-analysis

I want to prove Hadamard's inequality which is formulated as follows:

Let $X=(x_{ij})_{1\leq i,j\leq m}$ be the $m\times m$ real matrix.
Prove that $$|\det X|\leq \sqrt{\sum_{k=1}^m x_{1k}^2}\times \cdots
\times \sqrt{\sum_{k=1}^m x_{mk}^2}$$

It suffices to prove the following result:

Let $X=(x_{ij})_{1\leq i,j\leq m}$ be the $m\times m$ real matrix
such that $\lVert x_i\rVert=1$ for each $i\in [m]$, where
$x_i=(x_{i1},\dots,x_{im})$. Prove that $$|\det X|\leq 1.$$

I'll show my attempts which are based on Lagrange's multipliers method.

Proof attempt: Let $f:\mathbb{R}^{m^2}\to \mathbb{R}$ be defined as follows:
$$f(\vec{x})\equiv f(x_{11},\dots,x_{1m},\dots,x_{m1},\dots,x_{mm}):=\det \begin{pmatrix}
x_{11}\dots x_{1m}\\
\cdots \cdots \\
x_{m1}\dots x_{mm}
\end{pmatrix}.$$
Also define constraints functions $F_1,\dots, F_m:\mathbb{R}^{m^2}\to \mathbb{R}$ as follows: $$F_i(\vec{x})=(x_{i1})^2+\dots+(x_{im})^2-1 \quad \text{for each} \quad i\in [m].$$
Let $S:=\{x\in \mathbb{R}^{m^2}: F_1(x)=\dots=F_m(x)=0\}$. We notice that for each $x\in S$ the $\text{rank}(F_1(x),\dots,F_m(x))=m$ and hence $S$ defines $(m^2-m)$-dimensional smooth submanifold in $\mathbb{R}^{m^2-m}$.

Now we need to consider the following optimization problem: $\begin{cases} f\to \text{extremum}\\ x\in S\end{cases}$ or equivalently $f|_S\to \text{extremum}$ and my goal to show that $\big|f|_S(x)\big|\leq 1$.

Consider Lagrangian function $\mathcal{L}(\vec{x},\lambda)=f(\vec{x})-\sum\limits_{i=1}^m \lambda_i F_i(\vec{x})$. We know that if $\vec{x}_0\in S$ is local extremum of $f|_S$, then $(\vec{x_0},\widehat{\lambda})$ is a critical point of $\mathcal{L}(x,\lambda)$, where $\widehat{\lambda}\in \mathbb{R}^m$ follows from the necessary condition for extremum with constraints. Let's find critical point of $\mathcal{L}(x,\lambda)$, i.e.
$$\begin{cases}
\dfrac{\partial \mathcal{L}}{\partial x_{k\ell}}=\dfrac{\partial f}{\partial x_{k\ell}}(x)-\sum\limits_{i=1}^m \lambda_i \dfrac{\partial F_i}{\partial x_{k\ell}}(x)=0, \quad k,\ell\in [m] \\
\dfrac{\partial \mathcal{L}}{\partial \lambda_{i}}=-F_i(x)=0, \quad i\in [m]
\end{cases}$$
In order to find partial derivative of $f(x)$ which is a determinant function, we can write $f(x)=x_{i1}A_{i1}(x)+\dots+x_{im}A_{im}(x)$ which is basically a cofactor expansion of $f(x)=\det X$. Now we see that $\frac{\partial f}{\partial x_{ij}}(x)=A_{ij}(x)$. Also notice that $$\frac{\partial F_i}{\partial x_{k\ell}}=\begin{cases}
0, \quad \text{if}\ i\neq k\\
2x_{k\ell},\quad \text{if}\ i=k
\end{cases}$$

This implies that $$\begin{cases}
A_{k\ell}(x)=\lambda_k 2x_{k\ell}, \quad k,\ell\in [m]\\
F_i(x)=0, \quad i\in [m]
\end{cases}$$

Multiplying the first equation by $x_{k\ell}$ and summing over $1\leq\ell\leq m$ and using the fact that $F_k(x)=0$ it follows that $\lambda_k=f(x)/2$. Thus we were able to show that $\lambda_1=\dots=\lambda_k=f(x)/2$.

In particular, this implies that $A_{k\ell}(x)=x_{k\ell}f(x)$.
Assume that $f(x)\neq 0$, then the fact that $A_{k\ell}(x)=x_{k\ell}f(x)$ implies that $X^{-1}=X^T$, where $X=(x_{ij})$.
Hence $(\det X)^2=\det X \det X^T=\det XX^T=\det XX^{-1} =1$. It implies that $(f(\vec{x}))^2=1$.

Now I am confused and I'd like to ask the following questions:

  1. In the last paragraph I assume that $f(x)\neq 0$. But what happens if $f(x)=0$?

  2. So this argument show that if $x_0\in S$ is a local extremum of $f|_S$, then $f(x_0)^2=1$. But does it imply that $|f(x)|\leq 1$ for all $x\in S$ because this is what I want to prove eventually.

  3. All this argument makes sense if local extremum of $f|_S$ exists. But what if it does not exist?

I'd be grateful if someone can answer my questions and help me to finish the solution! Thank you!

Addendum: After reading @Youem's answer I was able to polish my proof. We notice that $S$ is a compact subset of $\mathbb{R}^{m^2}$ and hence the function $f|_S$ has a maximum and minimum at some points $x_M\in S$ and $x_m\in S$, respectively.

  1. We notice that $f(x_M)\geq 1$ because the point $\widehat{x}=(\underbrace{1,0,\dots,0}_{\text{$m$ elements}}, \underbrace{0,1,\dots,0}_{\text{$m$ elements}},\dots,\underbrace{0,0,\dots 1}_{\text{$m$ elements}})\in S$ and $f(\widehat{x})=1$ (I am doing this because I want to be sure that $f(x_M)\neq 0$). Applying what I've done above implies that $(f(x_M))^2=1$ and hence $f(x_M)=1$. Therefore, for all $x\in S$ we have $f(x)\leq 1$.

  2. Also we notice that $f(x_m)\leq -1$ because the point $\tilde{x}=(\underbrace{-1,0,\dots,0}_{\text{$m$ elements}}, \underbrace{0,1,\dots,0}_{\text{$m$ elements}},\dots,\underbrace{0,0,\dots 1}_{\text{$m$ elements}})\in S$ and $f(\tilde{x})=-1$ (I am doing this because I want to be sure that $f(x_m)\neq 0$). Applying what I've done above implies that $(f(x_m))^2=1$ and hence $f(x_m)=-1$. Therefore, for all $x\in S$ we have $f(x)\geq -1$.

Combining both conclusions we obtain that $\forall x\in S$, we have $|f(x)|\leq 1$.

Best Answer

  1. $f(x) = 0$ gives you trivially the inequality.

  2. Use the multilinearity of the determinant for $x\not\in S$.

  3. Local extremum will always exists because you are optimizing over a compact.

Related Question