1
$\begingroup$

I understand that the operator norm of a matrix is induced by the vector norm, and is given by

$$ \|A\|_{\rm op} = \max_{\|x\| = 1}\|Ax\| $$

However, in a lecture, I see the operator norm being mentioned as the following.

$$ \|A\|_{\rm op} = \max_{\|z\| = 1}|z^{\rm T}Az| $$

Note that in the latter definition we have the absolute value (as $z^{\rm T}Az$ is a scalar). For context, we know that $A$ is a real symmetric matrix with entries in $\{-1,1\}$. I am not able to see how these two definitions are the same. Any help would be amazing. Thanks!

$\endgroup$

2 Answers 2

3
$\begingroup$

If $A$ is real and symmetric, then $A$ is orthogonally diagonalisable with real eigenvalues. That is, there exists an orthonormal basis of eigenvectors $v_1, \ldots, v_n$, with respective eigenvalues $\lambda_1, \ldots, \lambda_n \in \Bbb{R}$. An arbitrary vector $x$ can be represented as a linear combination of this basis: $$x = a_1 v_1 + \ldots + a_n v_n.$$ We have, using Pythagoras's theorem, $$\|x\|^2 = \|a_1 v_1\|^2 + \ldots + \|a_n v_n\|^2 = |a_1|^2 + \ldots + |a_n|^2.$$ Applying $A$, we also get \begin{align*} \|Ax\|^2 &= \|a_1 Av_1 + \ldots + a_n Av_n\|^2 \\ &= \|a_1 \lambda_1 v_1 + \ldots + a_n \lambda_n v_n\|^2 \\ &= |a_1|^2 |\lambda_1|^2 + \ldots + |a_n|^2 |\lambda_n|^2. \end{align*} So, the problem of finding $\max_{\|x\| = 1} \|Ax\|^2$ is equivalent to maximising $|a_1|^2 |\lambda_1|^2 + \ldots + |a_n|^2 |\lambda_n|^2$, subject to $\|(a_1, \ldots, a_n)\| = 1$ (with the Euclidean norm). This quantity is maximised by biasing towards the largest value of $|\lambda_i|$, i.e. if $|\lambda_i| \ge |\lambda_j|$ for all $j$, then we get the maximum by setting $a_i = 1$ and each other $a_j = 0$.

In other words, any vector $x$ in the unit sphere which maximises $\|Ax\|^2$ is inevitably an eigenvector corresponding to one of the largest eigenvalues (in the sense that the absolute value is greatest). The actual maximum of $\|Ax\|^2$ is $|\lambda|^2$, where $\lambda$ is the largest eigenvalue. Thus, the operator norm $\|A\|$ by this definition should be $|\lambda|$.

Next, let's consider $\max_{\|x\|=1}|x^\top Ax|$. Let's keep the above linear combination for $x$ as before. Remembering that $v_1, \ldots, v_n$ is orthonormal, we get \begin{align*} |x^\top Ax| &= |x \cdot (Ax)| \\ &= |(a_1 v_1 + \ldots + a_n v_n) \cdot (a_1 \lambda_1 v_1 + \ldots + a_n \lambda_n v_n)| \\ &= |\lambda_1 a_1^2 + \ldots + \lambda_n a_n^2|. \end{align*} In similar fashion, we restrict $a_1^2 + \ldots + a_n^2 = 1$. If we have a largest eigenvalue $\lambda_i$, then $$|\lambda_1 a_1^2 + \ldots + \lambda_n a_n^2| \le |\lambda_1| a_1^2 + \ldots + |\lambda_n| a_n^2 \le |\lambda_i|(a_1^2 + \ldots + a_n^2) = |\lambda_i|,$$ an upper bound which is again achieved when $x$ is a corresponding eigenvalue $v_i$. Again, the maximum is simply the modulus of the largest eigenvalue, which agrees with the previous definition.

$\endgroup$
1
$\begingroup$

Since by the spectral theorem every real symmetric can be diagonalized as $Q^T D Q$ with $Q$ orthogonal and $D$ a real diagonal matrix, we can write the second definition as $$\|A\| = \max_{\|z\| = 1} ~ z^T A z = \max_{\|z\| = 1} ~z^T Q^T D A z = \max_{\|z\| = 1} ~(Qz)^T D (Qz) $$ But if we recall that every orthogonal matrix is an isometry (i.e. length-preserving and invertible), we know that $Qz$ returns a unit vector $y$ (and furthermore, for every unit vector $y$, there exists a unique $z$ such that $Qz = y$). Hence, maximizing $(Qz)^T D (Qz)$ over all unit vectors $z$ is equivalent to maximizing $y^T D y$ over all unit vectors $y$. Let the diagonal entries $d_i$ be arranged in decreasing order of absolute value, and let the $i$th entry of $y$ be $y_i$. Then we wish to maximize $$|y^T D y| = |d_1 y_1^2 + d_2 y_2^2 + \cdots + d_n y_n^2|, ~~\text{ subject to } y_1^2 + y_2^2 + \cdots + y_n^2 = 1$$ To see when the above inequality is maximized, note that the triangle inequality says that $$|d_1 y_1^2 + d_2 y_2^2 + \cdots + d_n y_n^2| \leq |d_1|y_1^2 + \cdots + |d_n| y_n^2 \leq |d_1| (y_1^2 + \cdots + y_n^2) = |d_1|$$ And we can observe that equality is obtained by choosing $y_1 = 1$ and the rest of the $y_i$ to be zero. In this definition, the operator norm is the the absolute value of the largest eigenvalue.

So why is the second definition the same? It's because $$\|A x\| = \sqrt{(A x)^T (Ax)} = \sqrt{x^T (A^T A ) x} = \sqrt{x^T A^2 x}$$ since $A$ is symmetric. But as $A^2$ is a symmetric matrix, we can use what we found in the previous section to conclude that the maximum of $x^T A^2 x$ over all unit $x$ is the absolute value of the largest eigenvalue of $A^2$. But that is exactly the square of the largest eigenvalue of $A$, so in taking the square root we see that the definitions do indeed match up.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .