Skip to main content
Post Undeleted by Suvrit
Post Deleted by Suvrit
Post Undeleted by Suvrit
applied cauchy-schwarz correctly this time!
Source Link
Suvrit
  • 28.6k
  • 7
  • 82
  • 150

The crux of the proof isMany thanks to indeed consider the Schur power matrix. Let $A$ be an $n\times n$ matrix. Then consider the $n! \times n!$ matrix $S(A)$ indexed by permutations $\sigma, \tau$ such that the $(\sigma,\tau)$-entry is given by $\prod_{i=1}^n a_{\sigma(i),\tau(i)}$Denis for $\sigma, \tau \in \mathfrak{S}_n$.

Schur's theorem. Let $A$ be a positive semidefinite matrix. Then, for any vector $x$, $x^TS(A)x \ge \det(A)x^Tx$.

It turnspointing out that actuallymy erroneous initial "proof". This time around the determinant of $A$proof is also an eigenvalue of $S(A)$ (and from the above theoremcorrect, it is the smallest eigenvalue). From thisand directly proves the Immanantal inequality also follows as a corollary. Let me repeat a proofassertion in line 3 of this claim below (this is not my original proofthe OP, obviously)i.

Proof. Consider the tensor product matrix $\otimes^n A$e., and augment $x$$\chi(e)\det(A)\le d_\chi(A)$ (which is a vector of dim $n!$) by padding with zeros appropriately to obtain a vectorI will write $z$ that is$d_\chi(I)$ instead of dim $n^n$, so that $$x^TS(A)x= z^T(\otimes^n A)z.~~~~~~~~~~~~~~~(*)$$ Since $A$ is psd, we can write $A=B^TB$$\chi(e)$ for a lower-triangular matrix $B$. Thus, we have (using simple properties of the tensor productuniformity) $$[z^T(\otimes^n A)z = z^T(\otimes^n B^TB)z = z^T(\otimes^n B^T)(\otimes^n B)z.$$.

Now by Cauchy-Schwarz we obtain \begin{align*} x^TS(A)x & \le \left[z^T(\otimes^n B^T)^2z\right]^{1/2}\left[z^T(\otimes^n B)^2z\right]^{1/2}\\ &= \left[z^T(\otimes^n (B^T)^2)z\right]^{1/2}\left[z^T(\otimes^n B^2)z\right]^{1/2}. \end{align*} Using the relation $(*)$ twice on the rhs above we thus obtain \begin{equation*} x^TS(A)x \le [x^TS(B^2)^Tx]^{1/2}[x^TS(B^2)x]^{1/2}. \end{equation*} Since $B^2$ is lower triangular, the diagonal entries of $S(B^2)$ are all easily seen to be actually equal to $\det(B^2)=\det(B)^2$. Moreover, $S(B^2)$ itselfThe explicit notation is lower-triangularcumbersome, so that $x^TS(B^2)x = \det(B)^2x^Tx$ which equals $\det(A)x^Tx$. Substituting this in the final inequality above, theI am just writing a proof is completesketch.

  1. First, recall that $d_\chi(A)=z^T(\otimes^n A)z$ for a suitable vector $z$
  2. Next, use Cauchy-Schwarz to obtain $$|z^T(\otimes^n (X^TY))z|^2 = |z^T(\otimes^n X^T)(\otimes^n Y)z|^2\le z^T(\otimes^n X^TX)z \cdot z^T(\otimes^n Y^TY)z$$
  3. Now write $A=C^TC$ for some upper triangular matrix $C$ (since $A$ is PSD we can do this). Then, put $X=C$ and $Y=I$ above, to obtain
  4. $|z^T(\otimes^n C)z|^2 = |z^T(\otimes^n I)z|^2|\det C|^2 \le |z^T(\otimes^n C^TC)z|\cdot |z^T(\otimes^n I)z|$, where we used the upper triangular nature of $C$ for the first step. In other words, we have shown that
  5. $d_\chi(I)^2 \det(A) \le d_\chi(A)d(I)$, since $|\det C|^2=\det(C^TC)=\det(A)$.

The crux of the proof is to indeed consider the Schur power matrix. Let $A$ be an $n\times n$ matrix. Then consider the $n! \times n!$ matrix $S(A)$ indexed by permutations $\sigma, \tau$ such that the $(\sigma,\tau)$-entry is given by $\prod_{i=1}^n a_{\sigma(i),\tau(i)}$ for $\sigma, \tau \in \mathfrak{S}_n$.

Schur's theorem. Let $A$ be a positive semidefinite matrix. Then, for any vector $x$, $x^TS(A)x \ge \det(A)x^Tx$.

It turns out that actually the determinant of $A$ is also an eigenvalue of $S(A)$ (and from the above theorem, it is the smallest eigenvalue). From this the Immanantal inequality also follows as a corollary. Let me repeat a proof of this claim below (this is not my original proof, obviously).

Proof. Consider the tensor product matrix $\otimes^n A$, and augment $x$ (which is a vector of dim $n!$) by padding with zeros appropriately to obtain a vector $z$ that is of dim $n^n$, so that $$x^TS(A)x= z^T(\otimes^n A)z.~~~~~~~~~~~~~~~(*)$$ Since $A$ is psd, we can write $A=B^TB$ for a lower-triangular matrix $B$. Thus, we have (using simple properties of the tensor product) $$[z^T(\otimes^n A)z = z^T(\otimes^n B^TB)z = z^T(\otimes^n B^T)(\otimes^n B)z.$$

Now by Cauchy-Schwarz we obtain \begin{align*} x^TS(A)x & \le \left[z^T(\otimes^n B^T)^2z\right]^{1/2}\left[z^T(\otimes^n B)^2z\right]^{1/2}\\ &= \left[z^T(\otimes^n (B^T)^2)z\right]^{1/2}\left[z^T(\otimes^n B^2)z\right]^{1/2}. \end{align*} Using the relation $(*)$ twice on the rhs above we thus obtain \begin{equation*} x^TS(A)x \le [x^TS(B^2)^Tx]^{1/2}[x^TS(B^2)x]^{1/2}. \end{equation*} Since $B^2$ is lower triangular, the diagonal entries of $S(B^2)$ are all easily seen to be actually equal to $\det(B^2)=\det(B)^2$. Moreover, $S(B^2)$ itself is lower-triangular, so that $x^TS(B^2)x = \det(B)^2x^Tx$ which equals $\det(A)x^Tx$. Substituting this in the final inequality above, the proof is complete.

Many thanks to Denis for pointing out my erroneous initial "proof". This time around the proof is correct, and directly proves the assertion in line 3 of the OP, i.e., $\chi(e)\det(A)\le d_\chi(A)$ (I will write $d_\chi(I)$ instead of $\chi(e)$ for uniformity).

The explicit notation is cumbersome, so I am just writing a proof sketch.

  1. First, recall that $d_\chi(A)=z^T(\otimes^n A)z$ for a suitable vector $z$
  2. Next, use Cauchy-Schwarz to obtain $$|z^T(\otimes^n (X^TY))z|^2 = |z^T(\otimes^n X^T)(\otimes^n Y)z|^2\le z^T(\otimes^n X^TX)z \cdot z^T(\otimes^n Y^TY)z$$
  3. Now write $A=C^TC$ for some upper triangular matrix $C$ (since $A$ is PSD we can do this). Then, put $X=C$ and $Y=I$ above, to obtain
  4. $|z^T(\otimes^n C)z|^2 = |z^T(\otimes^n I)z|^2|\det C|^2 \le |z^T(\otimes^n C^TC)z|\cdot |z^T(\otimes^n I)z|$, where we used the upper triangular nature of $C$ for the first step. In other words, we have shown that
  5. $d_\chi(I)^2 \det(A) \le d_\chi(A)d(I)$, since $|\det C|^2=\det(C^TC)=\det(A)$.
Post Deleted by Suvrit
Source Link
Suvrit
  • 28.6k
  • 7
  • 82
  • 150

The crux of the proof is to indeed consider the Schur power matrix. Let $A$ be an $n\times n$ matrix. Then consider the $n! \times n!$ matrix $S(A)$ indexed by permutations $\sigma, \tau$ such that the $(\sigma,\tau)$-entry is given by $\prod_{i=1}^n a_{\sigma(i),\tau(i)}$ for $\sigma, \tau \in \mathfrak{S}_n$.

Schur's theorem. Let $A$ be a positive semidefinite matrix. Then, for any vector $x$, $x^TS(A)x \ge \det(A)x^Tx$.

It turns out that actually the determinant of $A$ is also an eigenvalue of $S(A)$ (and from the above theorem, it is the smallest eigenvalue). From this the Immanantal inequality also follows as a corollary. Let me repeat a proof of this claim below (this is not my original proof, obviously).

Proof. Consider the tensor product matrix $\otimes^n A$, and augment $x$ (which is a vector of dim $n!$) by padding with zeros appropriately to obtain a vector $z$ that is of dim $n^n$, so that $$x^TS(A)x= z^T(\otimes^n A)z.~~~~~~~~~~~~~~~(*)$$ Since $A$ is psd, we can write $A=B^TB$ for a lower-triangular matrix $B$. Thus, we have (using simple properties of the tensor product) $$[z^T(\otimes^n A)z = z^T(\otimes^n B^TB)z = z^T(\otimes^n B^T)(\otimes^n B)z.$$

Now by Cauchy-Schwarz we obtain \begin{align*} x^TS(A)x & \le \left[z^T(\otimes^n B^T)^2z\right]^{1/2}\left[z^T(\otimes^n B)^2z\right]^{1/2}\\ &= \left[z^T(\otimes^n (B^T)^2)z\right]^{1/2}\left[z^T(\otimes^n B^2)z\right]^{1/2}. \end{align*} Using the relation $(*)$ twice on the rhs above we thus obtain \begin{equation*} x^TS(A)x \le [x^TS(B^2)^Tx]^{1/2}[x^TS(B^2)x]^{1/2}. \end{equation*} Since $B^2$ is lower triangular, the diagonal entries of $S(B^2)$ are all easily seen to be actually equal to $\det(B^2)=\det(B)^2$. Moreover, $S(B^2)$ itself is lower-triangular, so that $x^TS(B^2)x = \det(B)^2x^Tx$ which equals $\det(A)x^Tx$. Substituting this in the final inequality above, the proof is complete.