# Dual norm of the norm induced by inner product

Given a positive definite matrix A, let $$\langle x, y\rangle_A=x^\top Ay$$. This inner product induces a norm $$\|x\|_A^2=\langle x, x\rangle_A = x^\top A x$$. My question is, what is the dual norm of $$\|\cdot\|_A$$?

The goal is to get something like a Holder's inequality: $$|x^\top y|\leq \|x\|_A \|y\|_{A, *}$$ Note the LHS is the inner product in Euclidean space. Thanks a lot for any suggestions.

• I guess it is $\langle x, y\rangle_{A^\star}=x^T A^{-1} y$. – Giuseppe Negro Apr 5 '19 at 16:35
• Hi Guiseppe, thanks for your comment. If you first bound using Cauchy-Schwarz: $|x^\top y|^2\leq x^\top x y^\top y$ and compare to $x^\top A x y^\top A^{-1} y$, to make them equal one needs $A$ and $xy^\top$ to commute/simultaneous diagonalizable, this doesn't hold in general in this case I believe? – user3799934 Apr 5 '19 at 16:53
• I don't know, I was just guessing. Anyway, remember that it is enough to study the case of diagonal $A$; thus, $$\langle x, y\rangle_A=\lambda_1x_1y_1+ \lambda_2x_2y_2+\ldots + \lambda_nx_ny_n.$$ – Giuseppe Negro Apr 5 '19 at 17:05
• @GiuseppeNegro I believe I have a bound for diagonal A, but could u plz inform me why it suffices to study the diagonal case? Is it because you can do an eigendecomposition, and if the matrix multiplication is communtative, then you can cancel out terms? Thanks. – user3799934 Apr 5 '19 at 18:48
• Yes, symmetric matrices can be orthogonally diagonalized. – Giuseppe Negro Apr 5 '19 at 18:53

It holds that $$\lvert x^Ty\rvert^2 \le x^TAx\, y^TA^{-1}y,$$ (the right-hand side can be written $$\langle x,x\rangle_A \langle y, y\rangle_{A^{-1}}$$ in the notation of the OP).
Proof: the left-hand side of the inequality is invariant under the transformation $$x\mapsto Ox, y\mapsto Oy$$, where $$O$$ is an orthogonal matrix, and since $$A$$ is symmetric it is orthogonally diagonalizable. So there is no loss of generality in assuming that $$A=\text{diag}(\lambda_1,\lambda_2, \ldots, \lambda_n)$$, and since $$A$$ is positive definite, $$\lambda_j>0$$ for all $$j$$.
Now, setting $$\xi_j=\sqrt{\lambda_j} x_j,\qquad \eta_j=\frac{1}{\sqrt{\lambda_j}}y_j,$$ we see that $$|x^Ty|^2=|\xi^T\eta|^2\le \sum_{j=1}^n \xi_j^2\sum_{j=1}^n \eta_j^2=x^TAx\, y^TA^{-1}y,$$ and the proof is complete.
Let $$A = L L^T$$ be the Cholesky decomposition of $$A$$. Note that $$x^T A x = 1 \iff \| y \|_2^2 = 1$$ where $$y = L^T x$$.
The dual norm is \begin{align} \| z \|_* &= \sup_{x^T Ax = 1} \langle z, x \rangle \\ &= \sup_{\|y\|_2 = 1} \langle z, L^{-T}y \rangle \\ &= \sup_{\|y\|_2 = 1} \langle L^{-1} z, y \rangle \\ &= \| L^{-1} z \|_2 \\ &= \sqrt{z^T L^{-T} L^{-1} z } \\ &= \sqrt{z^T A^{-1} z}\\ &= \|z\|_{A^{-1}}\quad . \end{align}