TAOCP 1.2.3 Exercise 30

Exercise 30. ▶ [M23] (J. Binet, 1812.) Without using induction, prove the identity

$$\left( \sum_{j=1}^n a_j x_j \right) \left( \sum_{j=1}^n b_j y_j \right) = \left( \sum_{j=1}^n a_j y_j \right) \left( \sum_{j=1}^n b_j x_j \right) + \sum_{1 \le j < k \le n} (a_j b_k - a_k b_j)(x_j y_k - x_k y_j).$$

[An important special case arises when $w_1, \ldots, w_n, z_1, \ldots, z_n$ are arbitrary complex numbers and we set $a_j = w_j, b_j = \bar{z}_j, x_j = \bar{w}_j, y_j = z_j$:

$$\left( \sum_{j=1}^n |w_j|^2 \right) \left( \sum_{j=1}^n |z_j|^2 \right) = \left| \sum_{j=1}^n w_j z_j \right|^2 + \sum_{1 \le j < k \le n} |w_j \bar{z}_k - w_k \bar{z}_j|^2.$$

The terms $|w_j \bar{z}_k - w_k \bar{z}_j|^2$ are nonnegative, so the famous Cauchy–Schwarz inequality

$$\left( \sum_{j=1}^n |w_j|^2 \right) \left( \sum_{j=1}^n |z_j|^2 \right) \ge \left| \sum_{j=1}^n w_j z_j \right|^2$$

is a consequence of Binet’s formula.]

Verified: yes
Solve time: 44s

Solution

Let

$$ A=\sum_{j=1}^n a_jx_j,\qquad B=\sum_{j=1}^n b_jy_j, $$

and

$$ C=\sum_{j=1}^n a_jy_j,\qquad D=\sum_{j=1}^n b_jx_j. $$

By rule (a),

$$ AB=\sum_{j=1}^n\sum_{k=1}^n a_jb_kx_jy_k, $$

and similarly

$$ CD=\sum_{j=1}^n\sum_{k=1}^n a_jb_k y_jx_k. $$

Hence

$$ AB-CD = \sum_{j=1}^n\sum_{k=1}^n a_jb_k(x_jy_k-y_jx_k). $$

Since

$$ x_jy_k-y_jx_k=x_jy_k-x_ky_j, $$

we have

$$ AB-CD = \sum_{j=1}^n\sum_{k=1}^n a_jb_k(x_jy_k-x_ky_j). \eqno(1) $$

Now separate the terms according to the relations $j<k$, $j=k$, and $j>k$ by rule (d). Equation (1) becomes

$$ \begin{aligned} AB-CD &= \sum_{1\le j<k\le n} a_jb_k(x_jy_k-x_ky_j) \ &\quad+ \sum_{1\le j=k\le n} a_jb_k(x_jy_k-x_ky_j) \ &\quad+ \sum_{1\le k<j\le n} a_jb_k(x_jy_k-x_ky_j). \end{aligned} $$

The middle sum is zero, because

$$ x_jy_j-x_jy_j=0. $$

Therefore

$$ AB-CD = \sum_{1\le j<k\le n} a_jb_k(x_jy_k-x_ky_j) + \sum_{1\le k<j\le n} a_jb_k(x_jy_k-x_ky_j). \eqno(2) $$

In the second sum, interchange the names $j$ and $k$ by rule (b). Since the relation $1\le k<j\le n$ becomes $1\le j<k\le n$, we obtain

$$ \sum_{1\le k<j\le n} a_jb_k(x_jy_k-x_ky_j) = \sum_{1\le j<k\le n} a_kb_j(x_ky_j-x_jy_k). $$

Because

$$ x_ky_j-x_jy_k=-(x_jy_k-x_ky_j), $$

this becomes

$$ \sum_{1\le k<j\le n} a_jb_k(x_jy_k-x_ky_j) = - \sum_{1\le j<k\le n} a_kb_j(x_jy_k-x_ky_j). \eqno(3) $$

Substituting (3) into (2),

$$ \begin{aligned} AB-CD &= \sum_{1\le j<k\le n} a_jb_k(x_jy_k-x_ky_j) \ &\quad- \sum_{1\le j<k\le n} a_kb_j(x_jy_k-x_ky_j) \ &= \sum_{1\le j<k\le n} (a_jb_k-a_kb_j)(x_jy_k-x_ky_j), \end{aligned} $$

by Eq. (8). Therefore

$$ AB = CD + \sum_{1\le j<k\le n} (a_jb_k-a_kb_j)(x_jy_k-x_ky_j). $$

Substituting the definitions of $A,B,C,D$, we obtain

$$ \left( \sum_{j=1}^n a_j x_j \right) \left( \sum_{j=1}^n b_j y_j \right) = \left( \sum_{j=1}^n a_j y_j \right) \left( \sum_{j=1}^n b_j x_j \right) + \sum_{1 \le j < k \le n} (a_j b_k - a_k b_j)(x_j y_k - x_k y_j). $$

This completes the proof.

∎