Showing two norms on $\mathbb{R}^n$ are dual

Question

I am having trouble showing the following result.

If $A$ is a positive definite matrix, then the norms (on $\mathbb{R}^n$) $\|x\|_A:= \sqrt{x^\top A x}$ and $\|y\|_{A^{-1}}:= \sqrt{y^\top A^{-1} y}$ are dual.

[Here, the dual $\|\cdot\|^*$ of a norm $\|\cdot \|$ on $\mathbb{R}^n$ is defined to be $\|y\|^* := \sup_{x \in \mathbb{R}^n} \frac{y^\top x}{\|x\|}$.]

For $A$ being the identity matrix, the result follows from the Cauchy-Schwarz inequality: $y^\top x \le \|y\| \|x\|$ with equality attained when $x=y$, so $$\|y\|^* = \sup_{x \in \mathbb{R}^n} \frac{y^\top x}{\|x\|} = \|y\|.$$

However I am having trouble with general $A$. I tried using Cauchy-Schwarz on the inner product $\langle x,y \rangle = x^\top A y$, but got stuck. Any hints would be appreciated!

---

So I have some progress: going backwards from the stated result, I've shown that $$\frac{y^\top y}{\|y\|_A} = \frac{y^\top y}{\sqrt{y^\top A y}} = \sqrt{y^\top A^{-1} y} = \|y\|_{A^{-1}}$$ (I omitted my work), so that assuming $\|\cdot\|_{A^{-1}}$ is indeed the dual of $\|\cdot\|_A$, an $x$ that maximizes $\sup_{x \in \mathbb{R}^n} \frac{y^\top x}{\|x\|_A}$ is $x=y$.

However, I am still stuck on showing that $x=y$ indeed maximizes $\frac{y^\top x}{\|x\|_A}$. Cauchy-Swcharz (for the usual Euclidean norm) only gives $\frac{y^\top x}{\|x\|_A} \le \frac{\|y\|_2 \|x\|_2}{\|x\|_A}$ with equality if and only if $x$ and $y$ differ by a scalar, but the $\|x\|_A$ will mess things up.

Answer 1

$$ \left\|x\right\|_A^{*}= \displaystyle\sup_{_{\left\|y\right\|_A\leq 1}}y^{\perp}x =\sup_{_{\left\|A^{-1}y\right\|_A\leq 1}}\left(A^{-1}y\right)^{\perp}x =\sup_{_{\left\|y\right\|_{id}\leq 1}}\left(A^{-1}y\right)^{\perp}x =\sup_{_{\left\|y\right\|_{id}\leq 1}}y^{\perp}\left(A^{-1}x\right) =\left\|x\right\|_{A^{-1}} $$

I used the surjectivity of $A^{-1}$, the rest is calculus. $id$ is the identity matrix.

edit: use the root of $A$ instead of $A$ itself under the supremum. (see comments)

Answer 2

From Max's suggestions, we have the following. Note that positive definiteness of $A$ implies that $A^{1/2}$ and $A^{-1/2}$ exist and are both positive definite.

\begin{align*} \|y\|_A^* &= \sup_x \frac{x^\top y}{\sqrt{x^\top A x}} \\ &= \sup_x \frac{(A^{-1/2} x)^\top y}{\sqrt{x^\top A^{-1/2} A A^{-1/2} x}} & \text{$A^{-1/2}$ is symmetric and invertible} \\ &= \sup_x \frac{(A^{-1/2} x)^\top y}{\|x\|_2} \\ &= \sup_x \frac{x^\top (A^{-1/2} y)}{\|x\|_2} \\ &= \frac{\|A^{-1/2} y\|_2^2}{\|A^{-1/2}y\|_2} & \text{Cauchy-Schwarz, $x=A^{-1/2}y$} \\ &= \|A^{-1/2} y\|_2 \\ &= \|y\|_{A^{-1}}. \end{align*}

Answer 3

Here's an approach using Lagrange multiplers. Assume that $y \neq 0$. To evaluate $\| y \|_A^*$ we must find the optimal value for the optimization problem \begin{align} \tag{$\clubsuit$} \text{maximize} & \quad \langle y, x \rangle \\ \text{subject to } & \quad \frac12 x^T A x = \frac12. \end{align} (The optimization variable is $x$, and the factor of $1/2$ in the constraint is for convenience.) The Lagrangian for this problem is $$ L(x,\lambda) = \langle y, x \rangle - \frac{\lambda}{2} x^T A x - \frac{\lambda}{2}. $$ If $x$ is optimal then $$ \tag{$\spadesuit$}\nabla_x L(x,\lambda) = y - \lambda Ax = 0. $$ It follows from ($\spadesuit$) that $$ \langle y, x \rangle = \lambda x^T A x = \lambda. $$ So, the optimal value for problem ($\clubsuit$) is $\lambda$. This implies that $\lambda > 0$, because clearly the optimal value for ($\clubsuit$) is positive. Solving for $x$ in ($\spadesuit$) yields $x = (1/\lambda) A^{-1}y$. Now plugging this expression for $x$ into the constraint $x^T A x = 1$, we see that $$ (1/\lambda^2) y^T A^{-1} A A^{-1} y = 1 \implies \lambda^2 = y^T A^{-1} y \implies \lambda = (y^T A^{-1} y)^{1/2}. $$ We have discovered that the optimal value for ($\clubsuit$) is $$ \|y\|_A^* = (y^T A^{-1} y)^{1/2} = \| y \|_{A^{-1}}. $$