# Dual norm of a subspace of $\ell_\infty^3$

We define a norm on $$\mathbb C^2$$ as $$\|(\alpha,\beta)\|:=\max\left\{|\alpha|,|\beta|,\big|\frac{\alpha+\beta}{\sqrt{2}}\big|\right\}.$$ Can the dual norm be calculated explicitly?

$$\newcommand{\C}{\mathbb C}\newcommand{\R}{\mathbb R}\newcommand{\si}{\sigma}\newcommand{\al}{\alpha}\newcommand{\be}{\beta}$$This is to detail and correct the answer by Onur Oktay, which is based on a nice idea, leading to simplified and speedier calculations of the dual norm. (That Onur Oktay's answer contains at least two mistakes was pointed out in comments by Nathaniel Johnston and me.)

As in Onur Oktay's answer, let $$X:=\ell^3_\infty$$ and $$V:=\{av_1+bv_2:a,b\in\C\}\subset X$$, where $$\begin{equation*} v_1:=(1,0,1/\sqrt2),\quad v_2:=(0,1,1/\sqrt2),\quad v_3:=(1,1,-\sqrt2). \end{equation*}$$ Note that $$v_3\cdot v=0$$ for all $$v\in V$$, where $$\cdot$$ denotes the dot product. Consider
$$\begin{equation*} V^\perp:=\{x^*\in X^*\colon x^*(v)=0\ \forall v\in V\}, \end{equation*}$$ the so-called annihilator of $$V$$. Note that, if, as usual, $$X^*=(\ell^3_\infty)^*$$ is identified with $$\ell^3_1$$, then $$V^\perp$$ will be identified with the span $$\C v_3=\{tv_3\colon t\in\C\}$$ of $$\{v_3\}$$.

It is then said in Onur Oktay's answer that

$$V^*=X^*/V^\perp$$, which is isometrically isomorphic to $$\C^2$$ equipped with the norm $$\begin{equation*} \|(a,b)\|=\inf\{\|av_1+bv_2-tu\|_{\ell^3_1}: t\in\C\}, \end{equation*}$$

where $$u$$ is our $$v_3$$.

This statement is incorrect. First here is the minor point that $$V^*$$ is, not equal, but isometrically isomorphic to $$X^*/V^\perp$$ (Theorem 4.9), with the isometric isomorphism $$\si$$ given by the formulas $$\begin{equation*} V^*\ni v^*\mapsto\si(v^*):=x^*+V^\perp \end{equation*}$$ and $$\begin{equation*} \|x^*+V^\perp\|:=\inf\{\|x^*+y^*\|\colon y^*\in V^\perp\}, \tag{0}\label{0} \end{equation*}$$ where $$x^*\in X^*$$ is any extension of the continuous linear functional $$v^*$$. More importantly, the expression for $$\|(a,b)\|$$ in Onur Oktay's answer is incorrect.

Indeed, consider the isometric isomorphism $$\begin{equation*} \C^2\ni(\al,\be)\mapsto\iota((\al,\be)):=\al v_1+\be v_2\in V\subset X=\ell^3_\infty \end{equation*}$$ from $$\C^2$$ onto $$V$$, with the norm on $$\C^2$$ induced by $$\iota$$: $$\begin{equation*} \|(\al,\be)\|=\|\al v_1+\be v_2\|_\infty=\max(|\al|,|\be|,|\al+\be|/\sqrt2). \tag{1}\label{1} \end{equation*}$$ For any $$a$$ and $$b$$ in $$\C$$, define linear functionals $$l_{a,b}\in(\C^2)^*$$ and $$L_{a,b}\in V^*$$ by the conditions $$\begin{equation*} l_{a,b}((1,0))=a=L_{a,b}(v_1)\quad\text{and}\quad l_{a,b}((0,1))=b=L_{a,b}(v_2); \end{equation*}$$ here, of course, the norm $$\|\cdot\|_{(\C^2)^*}$$ on $$(\C^2)^*$$ is dual to the norm on $$\C^2$$ given by \eqref{1}. Also for $$a$$ and $$b$$ in $$\C$$, define the vector $$x_{a,b}\in\R^3$$ by the conditions $$\begin{equation*} x_{a,b}\cdot v_1=a,\quad x_{a,b}\cdot v_2=b,\quad x_{a,b}\cdot v_3=0, \end{equation*}$$ so that $$\begin{equation*} x_{a,b}=\tfrac14\,(3 a-b,3 b-a,\sqrt{2}(a+b)). \end{equation*}$$ So, the vector $$x_{a,b}\in\R^3$$ is the canonical representation of the extension -- say $$\tilde L_{a,b}$$ -- of the linear functional $$L_{a,b}\in V^*$$ such that $$\tilde L_{a,b}\in X^*=(\ell^3_\infty)^*\simeq\ell^3_1$$ and $$\tilde L_{a,b}(v_3)=0$$. The canonical representation of $$\tilde L_{a,b}$$ by $$x_{a,b}$$ here is of course the one induced by the canonical isometric isomorphism $$(\ell^3_\infty)^*\simeq\ell^3_1$$, so that $$\tilde L_{a,b}(x)=x\cdot x_{a,b}$$ for all $$x\in\ell^3_\infty$$.

Then $$l_{a,b}=L_{a,b}\circ\iota$$ and, in view of \eqref{0}, $$\begin{equation*} \|l_{a,b}\|_{(\C^2)^*}=\|L_{a,b}\|_{V^*} =\inf_{t\in\C}\|x_{a,b}+tv_3/4\|_1. \end{equation*}$$ Thus, $$\begin{equation*} \|l_{a,b}\|_{(\C^2)^*} =\tfrac14\,\min_{t\in\C}(|3 a - b + t|+|3 b-a + t|+\sqrt2\, |a + b - t|). \tag{2}\label{2} \end{equation*}$$

Finding the minimum in \eqref{2} is a problem of real algebraic geometry. So, in principle, the dual norm can be computed purely algorithmically; however, this calculation can take too much time -- as it actually is the case with the minimum in \eqref{2}.

However, finding the minimum in \eqref{2} numerically for any particular $$(a,b)\in\C^2$$ is not a problem. The numerical results obtained according to \eqref{2} completely agree with the numerical results obtained according to my other answer on this page, but the execution time using \eqref{2} is about 6 times as small.

As Matthew Daws noted in a comment, one could use the vector $$y_{a,b}:=(a,b,0)$$ in place of $$x_{a,b}=\tfrac14\,(3 a-b,3 b-a,\sqrt{2}(a+b))$$ -- in the sense that the linear functional $$X\ni x\mapsto x\cdot y_{a,b}$$ is, just as the linear functional $$\tilde L_{a,b}$$, an extension of the linear functional $$L_{a,b}$$. This results in an expression for $$\|l_{a,b}\|_{(\C^2)^*}$$ looking slightly simpler than the one in \eqref{2}: $$\begin{equation*} \|l_{a,b}\|_{(\C^2)^*} =\inf_{s\in\C}\|y_{a,b}+sv_3\|_1 =\min_{s\in\C}(|a + s|+|b + s|+\sqrt2\, |s|), \tag{2a}\label{2a} \end{equation*}$$ which seems to match the final expression in Nathaniel Johnston's answer. In fact, the ultimate expression in \eqref{2a} can be obtained from that in \eqref{2} by substitution $$t=a+b+4s$$.

• Your post reminds me an old timer's quote "the person who points out to me the scorpion on my dress has done a friendly deed" (although the translation made it sound like a Balki Bartokomous quote). Thanks for pointing out the gaps/mistakes in my post. Feb 25 at 6:01
• I am not sure what is "canonical" about the choice of $x_{a,b}$? It seems to me you could also choose (for example) $x_{a,b} = (a,b,0)$ and still have the correct dual pairing with $v_1$ and $v_2$. This choice immediately leads to an expression for the dual norm which agrees with Nathaniel Johnston's answer. Feb 25 at 9:50
• @OnurOktay : Thank you for your kind comment. Feb 25 at 13:31
• @MatthewDaws : Thank you for your comment. I have now completely detailed what $x_{a,b}$ is and does: "The canonical representation of $\tilde L_{a,b}$ by $x_{a,b}$ here is of course the one induced by the canonical isometric isomorphism $(\ell^3_\infty)^*\simeq\ell^3_1$, so that $\tilde L_{a,b}(x)=x\cdot x_{a,b}$ for all $x\in\ell^3_\infty$." Clearly, your $(a,b,0)$ in place of $x_{a,b}$ will not do. Feb 25 at 13:42
• But why do you need "$x_{a,b} \cdot v_3=0$"? Surely the only requirement is that $x_{a,b}$, restricted to the subspace $V$ induces the correct functional. My example does this, because $(a,b,0)\cdot v_1=a$ and $(a,b,0)\cdot v_2=b$ which is all you need. Feb 25 at 13:53

Let $$X=\ell^{3}_{\infty}$$ and let $$V=\{av_1+bv_2:a,b\in\mathbb{C}\}$$ be the subspace spanned by the vectors $$v_1 = (1, 0, \frac{1}{\sqrt{2}}) \hspace{9mm} v_2 = (0, 1, \frac{1}{\sqrt{2}}).$$ Let $$u = (1,1,-\sqrt{2})$$ so that $$u\perp V$$. Then, $$V^* = X^*/V^{\perp}$$, which is isometrically isomorphic to $$\mathbb{C}^2$$ equipped with the norm $$\begin{eqnarray} \|(a,b)\| &=& \inf\{\|av_1+bv_2-tu\|_{\ell^3_1}: t\in\mathbb{C}\} \\ &=& \inf\{|a - t| + |b - t| + |\frac{a + b}{\sqrt{2}} + \sqrt{2}t| : t\in\mathbb{C} \} \\ &=&\min\left\{ |b-a| + \frac{ |3a + b|}{\sqrt{2}} \hspace{1mm},\hspace{1mm} |b-a| + \frac{ |a + 3b|}{\sqrt{2}} \hspace{1mm},\hspace{1mm} \frac{ |a + 3b| + |3a+b|}{2} \right\}\\ \end{eqnarray}$$

• This is very nice. Just one request: Can you detail the derivation of the last equality in your answer? Feb 24 at 20:44
• Mathematica cannot find your $\inf$ even for $a=1$ and $b=i$. For these $a$ and $b$, the $\inf$ appears to be $3$ (attained at $t=0$), which is anyhow less than the value $\sqrt{10}$ of your (incorrect) $\min$. You appear to think that the $\inf$ is attained at one of the vertices of the triangle $\Big\{a,b,-\dfrac{a+b}2\Big\}$, but this is clearly not so. So, even after your simplification, the resulting problem of real algebraic geometry appears to be too hard for Mathematica. Feb 24 at 21:12
• Previous comment continued: Mathematica can (only barely) find the $\inf$ -- just for $a=1$ and $b=i$ -- only after receiving the hint that, because of symmetry and convexity, the minimizer $t$ must be of the form $s(1+i)$ for a real $s$. Thus, eventually Mathematica confirms that the $\inf$ for $a=1$ and $b=i$ is $3$. How, when the symmetry is not there (say when $a=1$ and $b=2i$), then Mathematica can do nothing. Feb 24 at 21:28
• "How, when" in the last sentence of the latter comment should of course be replaced by "However, when". Feb 24 at 22:23
• Regardless of my above comment, the optimization involving $t$ is a straightforward convex optimization problem that can be solved numerically by, for example, CVX in MATLAB extremely quickly. For example, if $a = 1$ and $b = 2i$ then the optimal value is approximate $4.52769...$, which is attained near $t = 0.2318 - 0.0854i$. Feb 25 at 0:35

This answer uses a lot of the same ideas as Onur Oktay's answer, but I believe corrects some problems with it. If we define $$\mathbf{e}_1 = (1,0)$$, $$\mathbf{e}_2 = (0,1)$$, $$\mathbf{u} = (1,1)/\sqrt{2}$$, and $$S = \{\mathbf{e}_1,\mathbf{e}_2,\mathbf{u}\}$$, then your norm is $$\|\mathbf{v}\| = \max_{\mathbf{w} \in S}\big\{|\langle \mathbf{w}, \mathbf{v}\rangle|\big\}.$$ By Theorem 2 of this paper (sorry for the self-citation; there's probably an earlier reference for this result, I just don't know what it is) it follows that the dual norm is $$\|\mathbf{v}\|^\circ = \min\big\{ |x|+|y|+|z| : \mathbf{v} = x\mathbf{e}_1 + y\mathbf{e}_2 + z\mathbf{u} \big\}.$$ This can be made more explicit by noting that the linear system $$\mathbf{v} = x\mathbf{e}_1 + y\mathbf{e}_2 + z\mathbf{u}$$ has a $$1$$-dimensional solution set given by $$(x,y,z) = (v_1, v_2, 0) + t(1,1,-\sqrt{2}),$$ where $$t \in \mathbb{C}$$ is arbitrary. It follows that $$\|\mathbf{v}\|^\circ = \min\big\{ |v_1+t|+|v_2+t|+\sqrt{2}|t| : t \in \mathbb{C} \big\}.$$ I'm not aware of a closed-form solution to this optimization problem, but it is convex and can be solved numerically very quickly by the CVX package for MATLAB, for example. Here is code that does the job and shows, for example, that this dual norm evaluated on the vector $$(1,1+i)$$ equals $$\sqrt{5}$$, which is attained when $$t = -(3+i)/5$$:

>> v = [1;1+i];

>> cvx_begin sdp quiet
>>     variable t complex;
>>     minimize abs(v(1)+t) + abs(v(2)+t) + sqrt(2)*abs(t)
>> cvx_end

>> cvx_optval

cvx_optval =

2.2361

>> t

t =

-0.6000 - 0.2000i

• In your expression $\|\mathbf{v}\|^\circ$, what linear functional (of what action) does $\mathbf{v}$ represent? Feb 25 at 5:56
• @IosifPinelis - I apologize if I'm misunderstanding your question, but the linear functional is just defined in the usual standard basis way: by $v_1$ I mean $\mathbf{v}(1,0)$ and by $v_2$ I mean $\mathbf{v}(0,1)$. Feb 25 at 18:37
• Thank you for the clarification. You seem to denote vectors and linear functionals with the same symbol $\mathbf v$, and I was unsure how the action of the linear functional $\mathbf v$ was defined and what $v_1$ and $v_2$ are. All this made it rather hard for me to read your answer. I suspect this was not a problem for people who, unlike me, had been previously exposed to these matters. Feb 25 at 19:02

This is a problem of real algebraic geometry. So, in principle, the dual norm can be computed purely algorithmically; however, this calculation can take too much time.

In Mathematica, this algorithm is implemented in the command Maximize. It has now been working for some time, with no result yet (click on the image of a Mathematica notebook below to magnify it):

Mathematica has so far been unable to even complete the calculation of the norm of a particular linear functional.