# Linear Algebra Tools for Proving Inequalities: Cauchy-Binet Formula

Leo Giugiuc has kindly communicated to me a problem from an artofproblemsolving forum. The problem is by the forum member kilua; the solution by Claudia Nanuti, Diana Trailescu, Dan Sitaru and Leo Giugiuc.

### Problem ### Cauchy-Binet Formula

Given a $k\times n\;$ matrix $A\;$, with $k\le n\;$ and an $n\times k\;$ matrix B. Let $J=(j_1,j_2,\ldots,j_k),\;$ $j_1\le j_2\lt \ldots\lt j_k\le n,\;$ be an ordered subset of $k\;$ out of $n\;$ indices. Define $A_J\;$ as the matrix obtained from $A\;$ by removing all columns that are not in $J\;$ and $B^J\;$ as the matrix obtained from $B\;$ by removing all rows that are not in $J.\;$ Then

Cauchy-Binet formula

$\displaystyle \det(AB)=\sum_{J}\det(A_J)\det(B^J),$

where the sum is taken over all subsets $J\subset\{1,2,\ldots,n\},\;$ $|J|=k.$

Corollary

For a $n\times k\;$ matrix $B,\;$ with $k\le n,$

$\displaystyle \det(B^tB)=\sum_J\left(\det(B^J)\right)^2.$

### Solution of the problem

We shall prove the following equivalent inequality:

$\displaystyle\left(\sum_{i=1}^{n}\frac{x_i^2}{a_i}\right)\left(\sum_{i=1}^{n}a_ix_i^2\right)\left(\sum_{i=1}^{n}a_iy_i^2\right)\ge \left(\sum_{i=1}^{n}\frac{x_i^2}{a_i}\right)\left(\sum_{i=1}^{n}a_ix_iy_i\right)^2+\sum_{i=1}^na_iy_i^2.$

Consider matrix $B=(b_{ij})_{1\le i\le n}^{1\le j\le 3},$ where $b_{i1}=\frac{x_i}{\sqrt{a_i}},\;$ $b_{i2}=x_i\sqrt{a_i},\;$ $b_{i3}=y_i\sqrt{a_i},\;$ $i=1,2,\ldots,n.\;$ Then

$\displaystyle B^tB=\left(\begin{array}{ccc} \sum_{i=1}^n\frac{x_i^2}{a_i} & 1 & 0\\ 1 & \sum_{i=1}^na_ix_i^2 & \sum_{i=1}^na_ix_iy_i\\ 0 & \sum_{i=1}^na_ix_iy_i & \sum_{i=1}^na_iy_i^2 \end{array}\right).$

The result follows immediately by the Cauchy-Binet formula (and a verification by the Cauchy-Schwarz inequality).

Thus

$\displaystyle\left(\sum_{i=1}^{n}\frac{x_i^2}{a_i}\right)\left(\sum_{i=1}^{n}a_ix_i^2\right)\left(\sum_{i=1}^{n}a_iy_i^2\right)\ge \left(\sum_{i=1}^{n}\frac{x_i^2}{a_i}\right)\left(\sum_{i=1}^{n}a_ix_iy_i\right)^2+\sum_{i=1}^na_iy_i^2.$

The equality holds for $n=2.\;$ Indeed, $rank(B)=rank(B^t)\le 2,\;$ such that $rank(B^tB)\le 2,\;$ implying $\det(B^tB)=0.$ ### Linear Algebra Tools for Proving Inequalities

$\;\left(\displaystyle\left(\frac{a}{b-c}\right)^2+\left(\frac{b}{c-a}\right)^2+\left(\frac{c}{a-b}\right)^2\ge 2\right)$
• An Inequality from Gazeta Matematica, March 2016 (If $a^2+b^2+c^2=3\,$ then $(a+c)(1+b)\le 4)$
• An Inequality from Gazeta Matematica, March 2016 II (If $x^2+y^2+z^2+t^2=1\,$ then $\;(x+z)(y+t)\le 4)$
• An Inequality from Gazeta Matematica, March 2016 III $\;(a^2+b^2+1\ge a+ab+b)$
• An Inequality from Gazeta Matematica, March 2016 IV (If $a^2+b^2+c^2=1\,$ then $a+ac+b\le 2)$
• Problem 3980 from Crux Mathematicorum $\;\left(\displaystyle\sum_{cycl}\frac{a+b}{a-b}\prod_{cycl}\frac{a+b}{a-b}\lt\frac{1}{3}\right)$
• NonSquare Matrix as a Tool for Proving an Inequality $\;\left(2(a + b + c)((a + 2b + 3c) \ge (\sqrt{b(a+b)} + 2\sqrt{c(b+c)} + \sqrt{a(c+a)})^2\right)$
• An Inequality in Parallelogram of Unit Area $\;\left(a^2+b^2+c^2+d^2+ac+bd\ge\sqrt{3}\right)$
• An Inequality from a Vietnamese Problem Book $\;\left(\displaystyle \frac{a^3+2}{b+2c}+\frac{b^3+2}{c+2a}+\frac{c^3+2}{a+2b}\ge 3\right)$
• Hadamard's Determinant Inequalities and Applications I $\left((2-a-b-c+abc)^2\le (a^2+2)(b^2+2)(c^2+2)\right)$
• Hadamard's Determinant Inequalities and Applications II $\left((n + a - 1)(a - 1)^{n-1} \le a^n\right)$
• 