Trace dual of the 
norm
Update: it turns out this isn’t quite right. Almost, but not quite. I need to fix this.
It turns out that the quantity I mentioned in the last post:
is indeed a norm on the set of symmetric matrices (here, 
is the largest (absolute) entry in 
). Furthermore, it is the trace dual of the 
norm I looked at earlier. This interesting fact is about all I’ve been able to show for my time in looking at this problem, so I provide my proof here.
First, to see that the quantity is well-defined, note that you can diagonalize any symmetric matrix, and write it as a sum of positive and negative definite matrices, for each of which such a factorization exists by Cholesky decomposition. Construct and 
appropriately from these factorizations, and we see that the set being minimized over is nonempty for any symmetric 
The only other nontrivial property is to see that the triangle inequality holds: let 
and 
be minimal factorizations, and note that
is a permissible factorization for 
This implies that 
Now we upper bound the trace-dual norm of 
. By definition,
Since such a 
has a decomposition 
where 
and 
— although not all such decompositions are minimal for the matrices they describe—, we have
Note that 
. Since 
this last quantity is actually 
. The 
and 
norms are dual, so
Recall that when 
is symmetric, 
and we have
But note that if 
is the vector at which 
is achieved, then 
is its own minimal decomposition, so
Therefore, 
and are trace dual norms.
Possibly relevant posts:
- Equivalence of the
norm and the 
norm (1/27/2010) - A failed attempt to use an SDP to find a nonorthogonal factorization (1/17/2010)
- Spectral spread of Graphs (7/30/2010)
norm of a PSD matrix