# Definitions of the operator norm of a matrix

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!

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.
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.