4
$\begingroup$

Let $(a_{ij})_{1 \le i,j \le n}$ be a real orthogonal matrix. Show that $\left| \sum_{1 \le i,j \le n} a_{ij}\right| \le n.$

Naively applying the Cauchy-Schwarz inequality only gives $n^{\frac{3}{2}}$ (but only relies on the columns being of norm $1$, and not orthogonality). How do we get the stronger bound $n$?

  • 2
    The Schwarz of inequality / And lemma too, he has no T. // The "Distri$b$ution" Schwartz you see / Is French, and so he has a T. -- R. P. Boas, *[Spelling Lesson](http://dx.doi.org/10.1007/BF03022860)*. :)2011-05-24

3 Answers 3

10

Let the vector $v$ be the sum of the row vectors. Think of this geometrically. Since we are adding $n$ orthonormal vectors, this vector is the diagonal of an $n$-dimensional box, and hence has norm $|v|=\sqrt{n}$.

Let $v_k$ refer to the entries of $v$. Then we have $\sum_{i,j} a_{ij}=\sum_k v_k\leq \sqrt{n \sum_k v_k^2}=n,$ by Cauchy Schwarz, and hence the original sum is bounded by $n$.

Hope that helps,

  • 0
    Yes, it did help. Thank you.2011-05-24
3

Use Cauchy-Schwarz on the product $^{\operatorname t}\!UMU$ where $U = ^{\operatorname t}\! \left( \begin{matrix} 1 & 1 & \dots & 1 \end{matrix} \right)$.

2

Let $A$ be your matrix, and let $u$ be the all ones vector (all its elements are equal to 1). Then the sum can be expressed as

$s = u^t A u$ = $u^t v$

Apply Cauchy-Schwarz to the vectors $u$ and $v$.