Group Invariance and Convex Matrix Analysis.
Certain interesting classes of functions on a real inner product space are invariant  under an associated group of orthogonal linear transformations.  This invariance can  be made explicit via a simple decomposition.  For example, rotationally invariant  functions on {\bf R}$^2$ are just even functions of the Euclidean norm, and functions on  the Hermitian matrices (with trace inner product) which are invariant under unitary  similarity transformations are just symmetric functions of the eigenvalues.  We  develop a framework for answering geometric and analytic (both classical and  nonsmooth) questions about such a function by answering the corresponding question  for the (much simpler) function appearing in the decomposition.  The aim is to  understand and extend the foundations of eigenvalue optimization, matrix  approximation, and semidefinite programming.
Introduction
Why is there such a strong parallel between, on the one hand, semidefinite
programming and other eigenvalue optimization problems, and on the other
hand, ordinary linear programming and related problems? Why are there
close analogies between many important matrix norms on the one hand, and
associated vector norms on the other? This paper aims to explain the simple
algebraic symmetries which drive these parallels.
A simple example may be illustrative. Suppose that we wish to understand
convex functions f which are 'orthogonally invariant'. By
this we mean that point x in R n and any orthogonal
matrix U . What can we say about such functions?
We might observe first that, since f is determined by its behaviour on the
where the function h : R+ ! R is defined by What conditions
on h are equivalent to the convexity of f? Clearly h must be convex (being
the restriction of f to a half-line), but this is not sufficient.
After some more thought we might arrive at the answer: h must be
convex, and nondecreasing at the origin. But this obscures the essential
symmetry of f . A simple trick allows us to preserve this in our answer.
Instead of examining the restriction of f to the half-line R+ e 1 we consider
the restriction to the whole subspace Re 1 . We then arrive at the much more
only if the function h
even and convex.
This easy example illustrates the fundamental technique of this paper:
analyzing the consequences of the symmetries of a function by analyzing its
symmetries on a 'transversal' (or defining) subspace. Von Neumann's famous
1937 characterization of unitarily invariant matrix norms [33] is precisely in
this mold. One statement of this result is that a unitarily invariant matrix
function f (one satisfying unitary u and v) is a norm
exactly when its restriction to the subspace of real diagonal matrices is a
symmetric gauge function.
What algebraic structure underlies von Neumann's result? There are
three essential ingredients: first, a real inner product space X (in this case
secondly, a (closed) group G of orthogonal
linear transformations (in this case those of the form x 7! uxv for unitary
u and v); thirdly, a map fl from X to a transversal subspace (in this case fl(x)
is the diagonal matrix with diagonal entries the singular values of x arranged
in nonincreasing order). The map fl should be G-invariant and idempotent,
and should satisfy the following conditions:
Axiom 1.1 (Decomposition) Any element x of X can be decomposed as
operator A in G.
Axiom 1.2 (Angle contraction) For any elements x and w in X, the
inequality hx; wi - hfl(x); fl(w)i holds, with equality if and only if x and w
have simultaneous decompositions,
operator A in G.
In von Neumann's case, Axiom 1.1 is just the singular value decomposition,
and Axiom 1.2 is 'von Neumann's Lemma' (see for example [7]).
This structure (X; G; fl) (which we call a normal decomposition system)
is the focus of this paper. Our aim is to analyze G-invariant functions on
via their restriction on the range of fl. For this to be of much interest
we would hope that the range of fl has lower dimension than X. Our other
main example, of fundamental interest in matrix optimization, also has this
property:
are the eigenvalues of x:
In a later paper [18] a broad family of examples generated from the theory
of semisimple Lie groups will be discussed. In this paper we concentrate
on outlining how the idea of a normal decomposition system provides
a simple yet powerful unifying framework in which to study a wide variety
of important results. Examples include Schur convexity (see for example
[22]), the convexity of eigenvalue functions ([10, 6, 11, 3, 13, 19]), calculations
of Fenchel conjugates and subdifferentials of convex eigenvalue functions
[24, 5, 12, 30, 28, 25, 26, 27, 15, 16, 1, 17, 19], von Neumann's original
result [33] and generalizations (for example [4, 20]), subdifferentials of unitarily
invariant norms [34, 35, 36, 37, 38, 8, 7, 9, 20], and characterizations
of extreme, exposed and smooth points of unit balls [2, 37, 38, 8, 7, 9, 20].
This paper concentrates on convexity and it ramifications. In a sequel we
consider derivatives of nonconvex functions, along the lines of [21].
Group invariant normal forms
Underlying all the work in this paper is a rather simple algebraic structure.
We therefore begin by fixing our notation and formally defining this structure.
We will work in a real inner product space X. For simplicity we will
assume that X is finite-dimensional, although many of our results extend
easily. The adjoint of a linear operator is the linear operator
A defined by hA   w; points w and x in X. We
denote the identity operator by id then we say that
A is orthogonal. In fact A is orthogonal if and only if it is norm-preserving:
where the norm is defined by In
this case, A
We denote the group of all orthogonal linear operators on X (with com-
position) by O(X), which we endow with the natural topology: thus A r
approaches A in O(X) if and only if A r x approaches Ax in X for all x
in X. Given a subgroup G of O(X), a function f on X is G-invariant if
and A in G. We can now describe our fundamental
structure: this structure is an underlying assumption throughout the
paper.
Definition 2.1 Given a real inner product space X and a closed subgroup G
of the orthogonal group O(X), the map induces a G-invariant
normal form on X if
(a) fl is idempotent,
(b) fl is G-invariant,
(c) for any point x in X there is an operator A in G with
(d) if points x and w lie in X then hx; wi - hfl(x); fl(w)i, with equality if
and only if some A in G.
In this case (X; G; fl) is called a normal decomposition system.
We defer a systematic discussion of examples until the end of the paper.
However, for the sake of concreteness the reader may wish to keep in mind the
following extremely simple example: (with
and jxj. The four properties are easily verified.
We will only use the closedness of G very rarely (specifically, in Theorem
3.3), but it does not rule out much of interest. Property (a) states that
points x in X. We think of the formula
in property (c) as being a 'normal form decomposition' of x. Clearly it
ensures that the map fl is norm-preserving:
Then property (d) expresses the fact that fl contracts the angle between the
vectors x and w unless they have a simultaneous normal form decomposition
(in which case the angle remains constant). If we write
then (c) says that G x is nonempty, while the condition for equality in (d) is
that G x " G w is nonempty.
Proposition 2.3 For points x and w in X,
Proof Note that hx; Awi - hfl(x); operator
A in G. On the other hand, since there exist operators B and C in G with
we have that hfl(x);
so the maximum is attained by
Given a subset K of X, the dual cone of K is defined to be the closed,
convex cone
The set K is a closed, convex cone if and only if
The function fl is K if the real function hfl(\Delta); wi is convex for all
vectors w in K, and a real function f
x and w in K satisfying
It transpires that Definition 2.1 has strong implications for possible maps
fl.
Theorem 2.4 The range R(fl) of the map fl is a closed, convex cone. Fur-
thermore, fl is norm-preserving, positively homogeneous and R(fl)
with global Lipschitz constant 1.
Proof For any point x in X it follows from Definition 2.1 that hx; wi -
hfl(x); wi for all points w in R(fl), and hence fl(x)\Gammax . If in particular
x lies in R(fl) ++ then
since, as we have seen, It follows that
hence R(fl) is a closed, convex cone.
Supposing once more that x lies in X and that the scalar - is nonnegative,
we have
whence positively homogeneous.
By Proposition 2.3, for any w in R(fl) we have
and hence hfl(\Delta); wi is convex, being a pointwise maximum of linear functions.
Thus fl is R(fl)
Finally, for any x and w in X,
whence the Lipschitz constant 1. 2
Various algebraic ideas can be applied naturally to the concept of a normal
decomposition system. For example, we say that two normal decomposition
systems are isomorphic if there is an
inner product space isomorphism and a group isomorphism
such that for all points x in X 1 and operators A in G 1 we have
There is also a natural notion
of the Cartesian product of two normal decomposition systems. Observe
finally that, given any inner product space X and subgroup G of O(X), taking
fl to be the identity map makes (X; G; fl) a normal decomposition system.
In fact easy examples show that this may be the only choice for fl with this
property.
3 G-invariant functions and sets
The main aim of this paper is to study functions f on the
inner product space X which are G-invariant:
in X and operators A in the group G. As usual we assume that the map fl
induces a G-invariant normal form on X in the sense of Definition 2.1.
We will be particularly interested in convex functions f , which we define
by requiring that the epigraph,
be a convex set. The function f is closed if its epigraph is closed, and is
proper if it never takes the value \Gamma1 and has nonempty domain,
dom
The (Fenchel) conjugate of f is the closed, convex function f
defined by
For proper, convex f , the conjugate f   is also proper, with f   providing
that f is also closed. For proper f we can define the (convex) subdifferential
at a point x in dom f by
Elements of the subdifferential are called subgradients. For all of these ideas
the standard reference is [29].
The following result is rather reminiscent of the discussion in [29, pp.
110,111]. It shows that conjugacy preserves G-invariance.
Proposition 3.1 If the function f G-invariant then so
is the conjugate function f   , and
for any point x in X.
Proof For any operator A in G w (whence
by Proposition 2.3. Since fl is G-invariant, so is f   . 2
Lemma 3.2 A G-invariant function differentiable
at the point x in X if and only if it is differentiable at fl(x).
Proof For any operator B in G, we know that
w in X, and hence by the chain rule, if f is differentiable at Bw then it is
differentiable at w. Choosing an operator A in G x (so that x = Afl(x)), the
result follows by setting
The next result is our first rather nontrivial observation. A consequence,
for example, is that symmetric, convex functions on R n are 'Schur-convex'
(see Example 7.1).
Theorem 3.3 If the G-invariant function
then it is R(fl) + -isotone on R(fl): if points x and w lie in R(fl) with
in
Proof The coset Gx is compact (since G is compact). If w lay outside
its convex hull then there would exist a separating hyperplane defined by a
vector v in X with
by Proposition 2.3, and then contradicting the assumption
that lies in R(fl) + . Hence there exist positive scalars
sum 1, and operators A 1 ; A 2 ; . ; A r in G with
Suppose that f(x) ! f(w). Then we can choose a real number ff in the
interval (f(x); f(w)), and since f is G-invariant, for each
r. Now since f is convex,
(see [29, Thm 4.2]), which is a contradiction. 2
We will also be interested in G-invariant subsets of X, so we will conclude
this section with some simple observations illustrating how various
algebraic and topological constructions preserve G-invariance. Notice first
that the class of G-invariant sets is easily seen to be closed under arbitrary
unions, intersections and complements. Suppose that the subset D of X is
G-invariant (that is, x 2 D; A 2 G implies Ax 2 D). Then the interior of D
is quickly seen to be G-invariant, whence the closure and boundary of D are
also G-invariant.
For each suppose that   r is a subset of R r , and define a
subset of X, ( r
It is immediate that this set is G-invariant. By taking   r to be R r , R r
in turn we see that the
linear hull, the conical hull, the affine hull and the convex hull of D are all
G-invariant. We say that a point x lies in the intrinsic core of D, written icr D, if
for any point w in the affine hull aff D, x lies in D for all real
sufficiently small. When D is convex its intrinsic core coincides with its
relative interior ri D, the interior of D relative to its affine hull (see [29]),
and in this case the relative boundary rb D is just cl D n ri D. Since it is easy
to check that icr D is G-invariant, it follows that for convex, G-invariant D,
the relative interior and boundary of D are also G-invariant. Finally, for any
G-invariant set D the dual cone D + and the orthogonal complement D ? are
both G-invariant.
Reduction
Let us assume once more that (X; G; fl) is a normal decomposition system, in
the sense of Definition 2.1. If the function f G-invariant
then since points x in X, the behaviour of f is determined
by its behaviour on R(fl), the range of fl. The key idea of this paper
is then rather simple: we reduce questions about f to corresponding questions
about the restriction of f to a subspace Y containing R(fl): typically,
Given a subspace Y of X, we denote the stabilizer of Y in G by
We will frequently abuse notation and write G Y for the group of restricted
operators G Y
In other words, we think of operators in G Y as orthogonal transformations on
Y (as well as on X). When Y contains R(fl) we can consider the restricted
frequently write fl in place of flj Y .
The following central assumption will remain in force through-out
the remainder of the paper.
Assumption 4.1 In the sense of Definition 2.1, (X; G; fl) is a normal decomposition
system. The inner product space Y is a subspace of X (with
the inherited inner product), and contains the range of fl. Furthermore,
is also a normal decomposition system.
This amounts to the additional assumption that if, in Definition 2.1, the
two points x and w in fact lie in Y then the operator A in properties (c) and
(d) can actually be chosen to leave Y invariant. Of course a trivial example
Once again, since we are deferring examples until the end of the
paper, it may be helpful to keep a simple (though nontrivial) example in
mind. We take X to be R n with the standard inner product, , the
orthogonal group on R n , and let e 1 be the vector (1; 0; 0; . ; 0). Then it is
easily verified that if we define x in R n then we obtain a
normal decomposition system, and that if then Assumption
4.1 holds.
An interesting general framework in which Assumption 4.1 holds is developed
in [18]. In summary, suppose that G is a real, semi-simple Lie group
with a maximal compact subgroup K, and that is the corresponding
Cartan decomposition (where g and k are the tangent algebras of G and
K respectively). Now let t, let the group G consist of the adjoint actions
of elements of K on t, and let Y be a maximal R-diagonalizable subspace of
t: then Gj Y is (essentially) the associated Weyl group. Finally, fix a closed
Weyl chamber D ae Y and for any point x in t define fl(x) to be the (single-
ton) intersection of the G-orbit of x with the chamber D. Then Assumption
4.1 holds: see [18] for details. In fact, all of the concrete examples which we
develop later fall into this framework.
In what follows, ffi denotes composition: thus (h
Proposition 4.2 A function f is G-invariant on X if and only if it can be
written in the form function h on Y .
Proof Any function of the form h ffi fl is G-invariant since fl is. If, on the
other hand, f is G-invariant then it is immediate that clearly
Thus henceforth we will restrict attention to G-invariant functions h
where the function h is G Y -invariant. We now follow two distinct approaches
to the elegant fact that such an extended-real-valued function h ffi fl is convex
on X if and only if h is convex on Y . The first approach is direct, using
Theorem 3.3, and hence relying on the underlying assumption that the group
G is closed. The second approach does not require this assumption, but
instead assumes that the function h is closed and employs an attractive
Fenchel conjugacy argument.
Theorem 4.3 (Convex and Closed Functions) Suppose that that function
-invariant. Then the function h ffi fl is convex
(respectively closed) on X if and only if h is convex (respectively closed) on
Y . Hence a G-invariant function on X is convex (respectively closed) if and
only if its restriction to Y is convex (respectively closed).
Proof Since one direction is clear. Conversely, suppose that
h is convex. For any points x and w in X and real - in (0; 1), we know by
Theorem 2.4 that -fl(x) +(1 \Gamma -)fl(w) and fl(-x +(1 \Gamma -)w) both lie in R(fl),
and that (-fl(x) lies in R(fl) + . Hence by
Theorem 3.3 (applied to the system (Y; G Y ; fl)), we have
Now for any real numbers ff ? h(fl(x)) and fi ? h(fl(w)), since h is convex
we deduce that h(fl(-x
[29, Thm 4.2].
Turning now to the closed case, since we have that
so that if h ffi fl is closed, then so is h. Suppose on the other hand that h
is closed. If ((x sequence of points in epi (h ffi fl) approaching the
point (x; r) then since the sequence ((fl(x i lies in the closed set epi h
and approaches (fl(x); r) (as fl is continuous by Theorem 2.4), it follows that
h, and so (x; r) 2
The second approach to convexity is rather more transparent once we
have derived the following elegant formula.
Theorem 4.5 (Conjugacy) Suppose that the function
is G Y -invariant. Then on the space X,
Proof By Proposition 3.1 applied in turn to the systems (X; G; fl) and
we see that for any point w in X,
is an immediate consequence of this conjugacy formula that a G Y -
invariant function (note that we exclude \Gamma1) is closed
and convex exactly when the function h ffi fl is closed and convex on X. One
direction is clear from equation (4.4). On the other hand, if h is closed and
convex then  by Theorem 4.5, and hence
closed and convex.
Proposition 4.2 shows that the restriction operator which maps an ex-
tended-real-valued function h on X to its restriction hj Y gives a one-to-
one correspondence between G-invariant functions on X and G Y -invariant
functions on Y . Theorem 4.3 (Convex and Closed Functions) show that
this correspondence preserves convexity and closedness, and the Conjugacy
Theorem (4.4) shows that it also preserves the conjugacy operation. We shall
see in Section 6 that restriction also preserves essential strict convexity and
smoothness (Corollary 6.3).
The next result provides perhaps a more compelling motivation for the
conjugacy approach. Recall that for a point x in X, the set G x describes the
possible decompositions of x: G
Theorem 4.6 (Subdifferentials) Given a function
which is G Y -invariant, suppose that the point x in X satisfies fl(x) 2 dom (h).
Then the element w of X is a subgradient of the function h ffi fl at x if and
only if fl(w) is a subgradient of h at fl(x) with x and w having simultaneous
decompositions: G x " G w 6= ;. In fact the following 'chain rule' holds:
Proof By definition, w 2 @(h ffi fl)(x) if and only if
using the Conjugacy Theorem (4.5). But then, since
equality holds throughout, and the first part of the result follows.
Suppose that w 2 @(h ffi fl)(x). Then by the above, fl(w) 2 @h(fl(x)) and
we can choose an operator A in G x " G w . Then
Conversely, suppose that y 2 @h(fl(x)) and that A 2 G x . Then
using the Conjugacy Theorem (4.5) and the G Y -invariance of h   . Thus Ay
lies in @(h ffi fl)(x), as required. 2
Notice that this result is the first point at which we have used the condition
for equality in property (d) of the definition of a normal decomposition
system (2.1).
Corollary 4.8 Suppose that the function f G-invariant
and that the point x lies in dom f . Then the element w of X is a subgradient
of f at x if and only if fl(x) is a subgradient of f at fl(x) with x and w having
simultaneous decompositions: G x " G w 6= ;. In fact
Proof Take in the Subdifferentials Theorem (4.6). 2
Corollary 4.9 Suppose that the function f G-invariant
and convex. If f is differentiable at the point x then
Proof By Lemma 3.2, f is differentiable at fl(x). By Corollary 4.8, since
5 Invariant sets
In th last section we studied G-invariant functions on the space X. In this section
we consider analogous questions for G-invariant subsets of X. As usual,
(X; G; fl) is a normal decomposition system, with a subsystem (Y; G Y ; fl)
(where Y contains the range of fl): in other words, Assumption 4.1 holds.
Proposition 5.1 A subset D of X is G-invariant if and only if it has the
subset C of Y .
Proof Clearly any set of the form fl G-invariant
because fl is. On the other hand, if D is G-invariant then it is
easily checked that we can write which has the required
Thus henceforth we will restrict attention to G-invariant sets fl \Gamma1 (C) (or
equivalently GC), where the set C ae Y is G Y -invariant. Sets can be effectively
studied via their indicator functions,
Notice for example that subset C of Y .
Corollary 5.2 (Closed and Convex Sets) Suppose that the subset C of
Y is G Y -invariant. Then the set fl \Gamma1 (C) is closed (respectively convex) if and
only if C is closed (respectively convex).
Proof Apply Theorem 4.3 to the function ffi C . 2
A fundamental idea in optimization is the (convex) normal cone to a
subset C of Y at a point y in C, defined by
It is easily checked that whence the following useful formula

Corollary 5.3 (Normal Cones) Suppose that the subset C of Y is G Y -
invariant and that the point x in X satisfies fl(x) 2 C. Then the element
w of X lies in the normal cone N(xjfl \Gamma1 (C)) if and only if fl(w) lies in
with x and w having simultaneous decompositions
In fact N(xjfl
Proof Apply the Subdifferentials Theorem (4.6) to the function
Other convex-analytic formulae follow easily from the Conjugacy Theorem
(4.5). For convenience we collect up some similar-looking results in a
single theorem. The polar set of a subset C of Y is defined by
while the polar cone is
Theorem 5.4 Suppose that the subset C of Y is G Y -invariant. Then
Furthermore if C is also convex then
(iv) ri fl
Proof An element w of X lies in (fl only if
whence (i), and (ii) is similar.
To see (iii), note that since fl may be regarded as a map from X to Y , and
is continuous by Theorem 2.4, fl \Gamma1 (int Y C) is an open subset of fl \Gamma1 (C), and
hence Conversely, suppose that the point x lies in
int (C). Then there is a sequence of points (y n )
in Y n C approaching fl(x). Each point has a decomposition y
for some operator A n in G Y , and since G Y is compact there is a convergent
subsequence A n 0 ! A 2 G Y . Now notice that the sequence fl(y n 0
approaches A   fl(x). Since fl \Gamma1 (C) is G-invariant, so is int
since x lies in int X fl \Gamma1 (C), so does A   fl(x). Thus for sufficiently large n 0 we
have fl(y since C is G Y -invariant,
which is a contradiction.
For any point y in C, y lies in Y and there is an operator A in G Y
with -invariant it follows that fl(y) 2 C, so that
Conversely, if y then again there exists
A in G Y with since C is G Y -invariant. Thus
Now suppose that C is convex and, without loss of generality, nonempty.
By Corollary 5.2, fl \Gamma1 (C) is a nonempty, G-invariant, convex set, so there
exists a point x in ri fl \Gamma1 (C). Since ri fl \Gamma1 (C) is G-invariant, fl(x) lies in
Hence the relative interiors of the convex sets fl \Gamma1 (C) and Y
intersect, so ri
it is elementary to check that aff (Y "
point z belongs to ri fl \Gamma1 (C) if and only if fl(z) ri C, by
the G-invariance of fl \Gamma1 (C), and (iv) follows. Equation (v) is similar. 2
The pattern of these results is clear. If the convex subset C of Y is
G Y -invariant then for many set operations '#' the following meta-
formula holds: #(fl
The utility of this formula lies in expressing the result of an operation in the
larger space X on a complicated set, fl \Gamma1 (C), in terms of the result of the
same operation in a smaller space Y on the simpler set C. A straightforward
deduction (in the light of Theorem 5.4) is that if the convex subset D of X
is G-invariant then for many set operations '#' the following meta-formula
holds:
We will see another example of this pattern in the next section: we will show
that exp (fl closed, convex set C, where exp C
denotes the set of exposed points of C. To end this section we prove the
analogous result for the set of extreme points of C, denoted ext C, which are
those points x in C for which C n fxg is convex.
Theorem 5.7 (Extreme Points) If the subset C of Y is convex and G Y -
invariant then ext (fl
Proof Suppose first that the point x in X does not belong to fl \Gamma1 (ext C),
so that fl(x) 62 ext C. If fl(x) 62 C then clearly x 62 ext (fl \Gamma1 (C)), so suppose
that for some points u and v in C distinct from fl(x) and some scalar ff in
(0; 1) we have ff)v. For any operator A in G x we now have
and since the points Au and Av are distinct
from x in the set fl \Gamma1 (C), it follows that x is not extreme in this set.
On the other hand, suppose that fl(x) is extreme in C and yet x is not
extreme in fl \Gamma1 (C): we will derive a contradiction. Pick points u 1 and v 1
distinct from x in fl \Gamma1 (C) and a scalar ff 1 in (0; 1) with
Now define a new point
lies in fl \Gamma1 (C), and if
by Theorem 2.4, with
Hence in either case fl(u) 6= fl(x). By defining a point v in an analogous
fashion we arrive at a representation
with fl(u) and fl(v) distinct from fl(x) in C.
Now certainly fl(x) does not belong to either of the cosets G Y fl(u) or
G Y fl(v): for example, if operator A in G Y then
applying fl gives a contradiction. Thus, since fl(x) is extreme,
Since the set on the right-hand-side is compact, we can choose an element y
of Y (defining a separating hyperplane) so that
using Proposition 2.3. But this contradicts the facts that
and the function hfl(y); fl(\Delta)i is convex (Theorem 2.4). 2
6 Smoothness, strict convexity, and invariant
norms
Our aim in this section will be to investigate the dual concepts of smoothness
and strict convexity for G-invariant convex functions. Once again, we assume
throughout that (X; G; fl) is a normal decomposition system, and that Assumption
4.1 holds, which is to say that is a subsystem where the
space Y contains the range of fl.
The first result shows that a G-invariant convex function h ffi fl (where the
function h is G Y -invariant - see Proposition 4.2) is differentiable at a point
x in X if and only if h is differentiable at fl(x).
Theorem 6.1 (Differentiability) Let the function
G Y -invariant. If hffifl is differentiable at a point x in X then h is differentiable
at fl(x), and the following chain rule holds:
r(h operator A 2 G x :
Conversely, if h is in addition convex, and differentiable at fl(x), then h ffi fl
is differentiable at x, and furthermore, fl(r(h
Proof For any operator A in G x we have and for all points y in
since h is G Y -invariant. The left-hand-side is differentiable at by the
chain rule, hence so is the right-hand-side, with
The first part of the result follows.
On the other hand, if h is also convex, and differentiable at fl(x), then
Now by the Subdifferentials
Theorem (4.6), if an element w of X belongs to @(h ffi fl)(x) then fl(w) 2
@h(fl(x)), and so In particular, since fl is norm-preserving
(Theorem 2.4), any such subgradient has norm krh(fl(x))k. Since @(h ffi fl)(x)
is a convex set and k \Delta k is a strict norm, @(h ffi fl)(x) has at most one element.
However, it is nonempty by the chain rule (4.7). Thus it is a singleton,
whence h ffi fl is differentiable at x by [29, ?], and the result follows. 2
We say that a proper, closed, convex function
essentially smooth if it is differentiable at any point where it has a subgra-
dient, and is essentially strictly convex if it is strictly convex on any convex
set on which the subdifferential is everywhere nonempty. These two concepts
are dual to each other: h is essentially smooth if and only if its conjugate is
essentially strictly convex, and vice versa [29, Thm 26.3].
Corollary 6.3 (Essential Smoothness and Strict Convexity) Suppose
that the function closed, proper and
convex. Then the function h ffi fl is essentially smooth (respectively essentially
strictly convex) if and only if h is essentially smooth (respectively essentially
strictly convex).
Proof Suppose first that h ffi fl is essentially smooth. If h has a subgradient
Y at the point y 2 Y then by Corollary 4.8 we have fl(v) 2 @h(fl(y)).
Since the identity operator lies in G fl(y) it follows from the subdifferential
formula (4.7) that fl(v) 2 @(h ffi fl)(fl(y)). Thus because h ffi fl is essentially
smooth, it is differentiable at fl(y), and hence by the Differentiability Theorem
(6.1), h is differentiable at fl(y), and therefore also at y by Lemma 3.2.
Thus h must be essentially smooth.
Conversely, suppose that h is essentially smooth. If h ffi fl has a subgradient
at a point x in X then the subdifferential formula (4.7) implies that
@h(fl(x)) is nonempty. Hence h is differentiable at fl(x), and therefore h ffi fl
is differentiable at x by the Differentiability Theorem (6.1). Thus h ffi fl is
essentially smooth.
The essentially strictly convex case follows by taking conjugates. 2
The following result is another example of the pattern (5.5) that we observed
in the last section: #(fl (#(C)). If the subset C of Y is
closed and convex then we say that a point y in C is exposed if there is an
element z of Y with hz; yi ? hz; ui for all points u in C n fyg. Equivalently,
a point y in C is exposed if and only if it lies in the range of rffi   C [29,
25.1.3]. We denote the set of exposed points by exp(C).
Corollary 6.4 (Exposed Points) Suppose that the subset C of Y is G Y -
invariant, closed and convex. Then
Proof If the point x in X satisfies fl(x) 2 exp(C) then for some element
v of Y we have and by Corollary 4.9 it follows that
C (fl(v)). Notice that hence by the Conjugacy
Theorem (4.5) we have
Choose an operator A in G x , so
that observe that A 2 G Afl(v) . Thus, applying the chain rule
(6.2),
so that x
Conversely, if x 2 exp(fl \Gamma1 (C)) then for some element w of X we have
It follows by the Differentiability Theorem
(6.1) that
To end this section we examine our results for the special case of invariant
norms. If p is a norm on Y then we denote the dual norm on Y by p D , where
for an element z of Y ,
We relate the dualizing operation for norms with conjugacy by the following
standard and straightforward trick.
Lemma 6.5 If p is a norm on Y then
A norm p on Y is smooth if it is differentiable except at the origin: equiv-
alently, the proper, closed, convex function p 2 =2 is essentially smooth. Fur-
thermore, p is strict if p(u distinct points u and v in the unit
ball for p, namely fy 2 Y j p(y) - 1g: equivalently, p 2 =2 is essentially strictly
convex. A point y in Y is a smooth point of the unit ball if
differentiable at y.
Theorem 6.6 (Norms) The G-invariant norms on X are those functions
of the form p ffi fl, where p is a G Y -invariant norm on Y . The dual of such a
norm is p D ffi fl. The norm p ffi fl is smooth (respectively strict) if and only if
p is smooth (respectively strict). A point x in X is an extreme (respectively
exposed, smooth) point of the unit ball for p ffi fl if and only if fl(x) is an
extreme (respectively exposed, smooth) point of the unit ball for p.
Proof By Proposition 4.2, the G-invariant functions on X are those of the
-invariant function on Y . If p ffi fl is actually a norm
on X then p is a norm on Y , since by G Y -invariance, p agrees with p ffi fl
on Y . Conversely, suppose that p is a G Y -invariant norm. Then certainly
(p points x in X, with equality if and only if
equivalently, Positive homogeneity of p ffi fl follows from
that of fl (Theorem 2.4). Finally, p ffi fl is convex by Theorem 4.3, and hence
is a norm.
By Lemma 6.5 we have
using the Conjugacy Theorem (4.5). Hence (p ffi fl) fl. The norm p ffi fl
is smooth if and only if (p essentially smooth, which by
Corollary 6.3 is equivalent to the essential smoothness of p 2 =2, and hence to
the smoothness of p. The strict case is analogous.
The last statement follows by applying the Extreme Points Theorem (5.7)
and the Exposed Points Corollary (6.4) to the unit ball for p, and by applying
the Differentiability Theorem (6.1) to p. 2
7 Examples
The idea of a normal decomposition system that we introduced in Definition
2.1 works well as an abstract mechanism. Its real significance however is
in the variety of examples that it models. In this section we discuss these
examples. They fall into two distinct categories: 'discrete' examples, where
the group G is a reflection group (in fact a 'Weyl group') and the range of
the map fl has full dimension in the underlying inner product space X, and
'continuous' examples, where fl maps X into a strictly smaller space Y . Both
categories are important for our purposes. Further discussion of the role of
Weyl groups in this construction may be found in [18].
First some notation for various sets of matrices. The trace of a matrix w
is denoted tr (w), and the Hermitian conjugate by w   .
The (multiplicative) group of n \Theta n real orthogonal matrices.
The (multiplicative) group of n \Theta n complex unitary
matrices.
The (multiplicative) group of n \Theta n permutation matrices.
: The (multiplicative) group of n \Theta n 'signed' permutation
matrices (having exactly one nonzero entry, \Sigma1, in each row
and each column.
product space of n \Theta n real symmetric matrices,
with
product space of n \Theta n complex Hermitian
matrices, with hw;
The inner product space of m \Theta n real matrices,
with
product space of m \Theta n complex matrices,
with
For a matrix w in S n or H n , the vector -(w) 2 R n has components the
eigenvalues of w, arranged in nonincreasing order. For a matrix w in M m;n (R)
or M m;n (C), the vector oe(w) 2 R l
the singular values of w, arranged in nonincreasing order.
Recall that a normal decomposition system consists of a real inner product
space X, a subgroup G of the orthogonal group on X, O(X), and a map
Example 7.1 (Reordering on R n ) We take (with the standard inner
(considered as a subgroup of O(R n in the natural
way), and where the vector -
arranged in nonincreasing order. The conditions in Definition 2.1 are immediate
except for (d), which states that
z in R n ,
with equality if and only if permutation matrix
A. Inequality (7.2) is classical: see for example [14, Thm 368]. The condition
for equality is not difficult: see [19, Lem 2.1].
The range of fl is R n nonincreasingg. The dual cone is
straightforward to compute: in fact, a vector z lies in (R n - only if
with equality for We say that a real function f on R n - is Schur convex
if f(x) - f(w) whenever x and w lie in R n - with (R Theorem 3.3
now shows that any symmetric, convex function is Schur convex [22, Prop.
3.C.2].
Example 7.3 (Absolute reordering on R n ) We take
and
and so forth. The conditions in Definition 2.1 are easy to check: (d) follows
from inequality (7.2).
Diagonal matrices will play an important role in our continuous examples.
We denote the smaller of the two dimensions m and n by l = minfm; ng,
and then we define a map Diag : R l !M m;n (C) by
(Diag
0; otherwise.
Example 7.4 (Symmetric matrices) We take G to be the
group of orthogonal similarity transformations x 7! u T xu for symmetric matrices
x and orthogonal matrices u. Finally, we define
More formally, define the adjoint representation of O n on S n , which we
orthogonal u and symmetric
x. Then G is just the range of this representation, which has kernel
f\Sigmaidg, and so G is isomorphic to O n =f\Sigmaidg.
Let us check the conditions of Definition 2.1. Condition (a), the idempotence
of fl, is self-evident. Condition (b), the G-invariance of fl, amounts to
the invariance of the set of eigenvalues under orthogonal similarity. Condition
(c), the decomposition axiom, follows from the spectral decomposition.
Condition (d), the angle contraction axiom, becomes the following inequality:
tr (wx) - h-(w); -(x)i; for all w; x
with equality if and only if there exists orthogonal u with (Diag -(x))u
and (Diag -(w))u. The inequality appears in [23], for example, and
the conditions for equality may be found in [31], using algebraic techniques.
A variational proof is given in [19]. The result is closely connected with
earlier work of von Neumann - see Example 7.6.
The natural choice for the subspace Y is the space of diagonal matrices
Diag R n . A standard calculation shows that an orthogonal u has Ad(u) in
the stabilizer G Y if and only if
n . However, since
(Ad(Diag (\Sigma1; \Sigma1; . ;
we see that the group G Y acting on the space Y of diagonal matrices is simply
the permutation group P n acting on the diagonal entries.
Notice also that for any vector ff in R n we have fl(Diag
ff. Hence
the subsystem (Y; G Y ; fl) is a normal decomposition system isomorphic to the
'reordering' system described in Example 7.1. In particular, Assumption 4.1
holds, so that all of the machinery that we have developed can be applied.
We list some consequences in the final section.
Example 7.5 (Hermitian matrices) The complex analogue of the previous
example is very similar (and there is a quaternionic analogue). We
which we emphasize we consider as a real inner product space
(since we are primarily concerned with properties of real vector spaces, such
as convexity). The group G now consists of unitary similarity transformations
x 7! u   xu for Hermitian x and unitary u, and as before,
Formally, we define the adjoint representation of U n on H n ,
unitary u and Hermitian x. Then G
is just the range of this representation, which has kernel Tid, where T is the
circle group f- 2 C j 1g. Thus G is isomorphic to U n =Tid. Checking
Definition 2.1 is entirely analogous to the previous example.
An aside is illustrative at this point. If we choose the subspace Y as
then the stabilizer G Y acts on Y exactly as AdO n . Thus in this case
the subsystem (Y; G Y ; fl) is a normal decomposition system isomorphic to
the previous, 'symmetric matrix' example (7.4). In particular, Definition 4.1
holds. The natural choice however is again to choose Y as the subspace of diagonal
matrices Diag R n . Then it is once again straightforward to identify the
action of the stabilizer G Y on this subspace with the permutation group P n
acting on the diagonal entries. Thus the subsystem (Y; G Y ; fl) is a normal
decomposition system isomorphic to the 'reordering' system, Example 7.1.
Again Assumption 4.1 holds, so our machinery applies.
Example 7.6 (Real matrices) We take (R) and G to be the
group of transformations x 7! u T xv for orthogonal matrices u in Om and v
in O n . Then we define
Formally, we define a representation of Om \Theta O n on M m;n (R), written
G is the range
of this representation: since the kernel of Ac is just f\Sigma(id; id)g, the group G
is isomorphic to (Om \Theta O n )=f\Sigma(id; id)g.
Checking Definition 2.1, the idempotence of fl is again clear, and G-invariance
amounts to the invariance of the set of singular values under the
transformations we consider. Condition (c), the decomposition axiom, follows
from the singular value decomposition, and condition (d), the angle
contraction axiom, becomes 'von Neumann's Lemma' [33]:
tr (w T x) - hoe(w); oe(x)i; for all w; x 2 M m;n (R);
with equality if and only if w and x have a simultaneous singular value
(Diag oe(w))v and (Diag oe(x))v for some u in
Om and v in O n (see the discussion in [7]).
The natural choice for Y is the space of diagonal matrices Diag R l (where
little thought then identifies the action of the stabilizer
G Y on the space Y with the group of transformations Diag (ff) 7! Diag (pff),
for a vector ff in R l and a matrix p in P \Sigma
l : to see this, note that any such
transformation clearly belongs to G Y , whereas on the other hand a transformation
in G Y must preserve diagonality and the singular values.
Notice also that fl(Diag vector ff in R l . Thus the subsystem
is a normal decomposition system isomorphic to the 'absolute
reordering' system described in Example 7.2. Since Assumption 4.1 holds,
our machinery applies: some consequences appear in the final section.
Two special cases deserve mention. The case exactly the example
discussed after Assumption 4.1. The even more special case
gives our very first example of a normal decomposition system, discussed after
Definition 2.1.
Example 7.8 (Complex matrices) The complex analogue of the previous
example is very similar (and again there is a quaternionic analogue). We
G to be the group of transformations x 7! u   xv for a
matrix x in M m;n (C) and unitary matrices u in Um and v in U n . Once again
we define
Formally we define a representation of Um \Theta U n on M m;n (C), written
G is the range
of this representation. Since the kernel of Ac is easily checked to be T(id; id)
(where T is once again the circle group), we see that the group G is isomorphic
to (U m \Theta U n )=Tid. Checking Definition 2.1 is analogous to the previous
example. In fact if we choose (R) then the subsystem (Y; G Y ; fl) is
isomorphic to the previous example.
If we make the natural choice for Y , namely the space of real diagonal
matrices Diag R l , then a similar argument to the previous example identifies
the action of the stabilizer G Y on the space Y as the group of transformations
Diag (ff) 7! Diag (pff), for a vector ff in R l and a matrix p in P \Sigma
l . Thus just
as in the previous example, the subsystem (Y; G Y ; fl) is isomorphic to the
'absolute reordering' system, Example 7.2. Again, all our machinery applies.
8 Consequences for matrix functions
In this concluding section we consider how our results can be applied to the
examples in the previous section to derive a variety of interesting results in
the literature. We begin with the case of symmetric matrices, Example 7.4.
The complex analogue is entirely similar, and we do not pursue it.
Symmetric matrices
A function h : R n ! [\Gamma1; +1] is symmetric if for any vector ff in
R n the value h(ff) is unchanged by permuting the components of ff: using
the notation of Example 7.1, Similarly, a subset C of R n is
symmetric when ff 2 C if and only if -
function on the space of
orthogonally invariant
matrices x in S n and u in O n : such functions
have also been called spectral [13]. Analogously, a subset D of S n is weakly
orthogonally invariant if u T xu 2 D whenever x 2 D (for orthogonal u).
The following result follows immediately by applying our machinery to
Example 7.4. We make no attempt to be exhaustive.
Theorem 8.1 (Convex spectral functions) Weakly orthogonally invari-
ant, extended-real valued functions on S n are exactly those functions of the
Such a function
on S n is convex (respectively closed, essentially strictly convex, essentially
smooth) if and only if h is convex (respectively closed, essentially strictly
convex, essentially smooth). For any such symmetric function h we have
Suppose further that some symmetric matrix x satisfies -(x) 2 domh.
Then the symmetric matrix w is a subgradient of h ffi - at x if and only if
-(w) is a subgradient of h at -(x) and x and w have simultaneous spectral
(Diag -(x))u and (Diag -(w))u for some
orthogonal matrix u. In fact the following 'chain rule' holds:
If h is convex then h ffi - is differentiable at x if and only if h is differentiable
at -(x).
Example 8.3 (The log barrier) Let us define a symmetric function h :
otherwise.
Then h is a closed, convex function , essentially smooth and essentially
strictly convex, with conjugate
otherwise.
It follows that the matrix function h defined by
positive definite,
otherwise,
is also closed, convex, essentially smooth and essentially strictly convex, with
conjugate
negative definite,
otherwise.
It is easy to check, using the chain rule, that for a positive definite symmetric
The convexity part of Theorem 8.1 was first proved in [6]. It was rediscovered
in [3]. A characterization of convexity in the differentiable case was
proved in [13], via Schur convexity, and the closed case was proved via the
conjugacy formula (8.2) in [19]. The latter paper also contains the remainder
of Theorem 8.1. A proof appears in [32] that h ffi - is analytic at x if and
only if h is analytic at -(x): some somewhat related results appear in [21].
Numerous formulae for subgradients of specific matrix functions appear, for
example, in [26, 27, 15, 16]: the chain rule in Theorem 8.1 provides a simple
unified approach to these.
Theorem 8.4 (Spectral convex sets) Weakly orthogonally invariant sub-sets
of S n are exactly those sets of the form - \Gamma1 (C) for symmetric subsets
C of R n , If the symmetric matrix x has -(x) in the symmetric set C then a
symmetric matrix w lies in the normal cone N(xj- \Gamma1 (C)) if and only if -(w)
lies in N(-(x)jC) with x and w have simultaneous spectral decompositions,
(Diag -(x))u and (Diag -(w))u for some orthogonal matrix u.
In fact
Furthermore,
int (-
Diag
The set - \Gamma1 (C) is convex (respectively closed) if and only if C is convex
(respectively closed). If C is convex then
ri (-
and if C is in addition closed then
Example 8.5 (The simplex) Let us define a symmetric subset of R n by
Then C is a closed, convex set with the standard unit vectors as extreme (in
fact exposed) points. We deduce that the set of symmetric matrices
positive semidefinite; tr
is closed and convex, with extreme (exposed) points yy T for unit column
vectors y in R n .
The fact that the set - \Gamma1 (C) is convex if and only if C is convex, for a
set C, was proved in [11].
Unitarily invariant norms
A function h : R l ! [\Gamma1; +1] is absolutely symmetric if the value h(ff)
at a vector ff in R l is independent of the order and signs of the components
in the notation of Example 7.3, In particular, if
such a function is also a norm then it is called a symmetric gauge function.
A matrix function unitarily invariant
if f(u   matrix x in M m;n (C) and unitary matrices u and
v. The following result is a consequence of applying our machinery to Example
7.8. The real analogue is entirely similar. For brevity, we restrict
ourselves to the norm case.
Theorem 8.6 (Unitarily invariant norms) Unitarily invariant norms on
m;n (C) are exactly those functions of the form h ffi oe for symmetric gauge
functions h on R l (where l = minfm; ng). In this case the dual norm is given
by (p ffi oe)
oe is smooth (respectively strict) if and only if p is smooth (respectively
strict), and a matrix x is an extreme (respectively exposed, smooth) point of
the unit ball for p ffi oe if and only if oe(x) is an extreme (respectively exposed,
smooth) point of the unit ball for p. Furthermore, a matrix w is a subgradient
of p ffi oe at x if and only if oe(w) is a subgradient of p at oe(x), with x and w
having simultaneous singular value decompositions (Diag oe(x))v and
(Diag oe(w))v for unitary matrices u and v. In fact,
The classical examples are the symmetric gauge function k \Delta k p (for 1 -
- 1), which give the 'Schatten p-norms', and the functions
which give the 'Ky Fan k-norms'.
The fundamental characterization of unitarily invariant norms is due to
von Neumann [33]. He proved the result in an analogous fashion to our
conjugacy argument following Theorem 4.5, by proving the duality formula
via his Lemma (7.7). Some interesting analogous results appear in [4].
The characterization of extreme, exposed, and smooth points was proved in
[2]: see also [37, 38, 8, 7, 9]. Versions of the subdifferential formula appear
in [35, 36].



--R

Optimization over the positive definite cone: interior point methods and combinatorial applications.
On the geometry of the unit ball of unitary matrix spaces.
Convexity conditions and existence theorems in nonlinear elasticity.
Concave gauge functions and applica- tions
The minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices.
All convex invariant functions of hermitian matrices.
Exposed faces and duality for symmetric and unitarily invariant norms.
Faces and traces of the unit ball of a symmetric gauge function.
Faces of the unit ball of a unitarily invariant norm.
On a theorem of Weyl concerning eigenvalues of linear trans- formations
Some convexity theorems for matrices.

Convex spectral functions.
Cambridge University Press
Sensitivity analysis for a class of convex functions defined over a space of symmetric matrices
Sensitivity analysis of all eigenvalues of a symmetric matrix.
An interior-point method for minimizing the maximum eigenvalue of a linear combination of matrices
Von Neumann's lemma and a Chevalley-type theorem for convex functions
Convex analysis on the Hermitian matrices.
The convex analysis of unitarily invariant functions.
Derivatives of spectral functions.
Inequalities: theory of majorization and its applications.
On the trace of matrix products.
Interior point polynomial methods in convex programming.
On minimizing the maximum eigenvalue of a symmetric matrix.

Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices.
A nondifferentiable optimization algorithm for structural problems with eigenvalue inequality constraints.
Convex Analysis.
Extremal problems on the set of nonnegative definite ma- trices
An inequality for the trace of the product of two symmetric matrices.
On analyticity of functions involving eigenvalues.
Some matrix inequalities and metrization of matric- space
An algorithm for optimal l 2 scaling of matrices.
Characterization of the subdifferential of some matrix norms.
On matrix approximation problems with Ky Fan k norms.
On the characterization of the extremal points of the unit sphere of matrices.
Subdifferentials, faces and dual matrices.
--TR
convexity;semidefinite program;fenchel conjugate;von Neumann's lemma;spectral function;extreme point;group invariance;nonsmooth analysis;unitarily invariant norm;schur convex;eigenvalue optimization;subdifferential