BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR92-1283 
ENTRY:: 1993-10-14
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: On Branching Numbers of Normal Manifolds
AUTHOR:: Ralph, Daniel
DATE:: May 1992
PAGES:: 21
NOTES:: replaces 91-1255
ABSTRACT::
Let $\cal M$ be a finite piecewise linear (pl) manifold of $IR^n$, and $P$ 
: $IR^n \rightarrow IR^n$ be pl with respect to $\cal M$, i.e. $P$ is 
affine on each set in $\cal M$. The branching number of $\cal M$, Kuhn 
and Lowen [8], is the maximum number of sets in $\cal M$ that can contain 
any common face of codimension 2. [8, Thm. 5.3] shows that if $\cal M$ has 
branching number less than or equal to 4, then $P$ is a homeomorphism if 
and only if it is coherently oriented, i.e. the determinants of $P$ on the 
sets in $\cal M$ have the same nonzero sign.

Let $C$ be a nonempty polyhedral convex set in $IR^n$, and $A \in 
IR^{nxn}$. Robinson [14] defines a finite pl manifold $\cal N_C$ of $IR^n$ 
called the normal manifold of $C$; and the normal map $A_C$ : 
$IR^n \rightarrow IR^n$ induced by ($A, C$), which is pl with respect to 
$\cal N_C$. [14, Thm. 4.3] shows that $A_C$ is homeomorphic if and only if it 
is coherently oriented.

We show that $\cal N_C$ has branching number less than or equal to 4, hence 
Robinson's result is actually a corollary of Kuhn and Lowen's.

Key Words: Piecewise linear, piecewise affine, branching number, normal 
map, pl-normal, normal manifold, homeomorphism, coherently oriented.
END:: CORNELLCS//TR92-1283 
BODY::
On Branching Numbers of Normal Manifolds*
Daniel Ralph
TR 92-1283
(replaces TR 91-1255)
May1992
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
*This research was supported in part by the U.S. Army Research Office through the
Mathematical Sciences Institute, Cornell University and in part by the National
Science Foundation, the Air Force Office of Scientific Research and the Office of
naval research, under grant DMS-8920550.
On Branching Numbers of Normal
Manifolds 1
Daniel Ralph
Cornell University
Department of Computer Science, Upson Hall
Ithaca, NY 14853
November 1991. Revised February 1992.
1This research was supported in part by the U.S. Army Research Office through
the Mathematical Sciences Institute, Cornell University, and in part by the Na-
tional Science Foundation, the Air Force Office of Scientific Research, and the
Office of Naval Research, under grant DMS-8920550.
Abstract
Let M be a finite piecewise linear (pi) manifold of 1R?, and P : lR? ? lR? be
pi with respect to M, i.e. P is affine on each set in M. The branching n?mber
of M, Kuhn and L5wen [8], is the maximum number of sets in M that can
contain any common face of codimension 2. [8, Thm. 5.3] shows that if M
has branching number less than or equal to 4, then P is a homeomorphism
if and only if it is coherently oriented, i.e. the determinants of P on the sets
in M have the same nonzero sign.
Let C be a nonempty polyhedral convex set in lR?, and A E lRnxn Robin-
son [14] defines a finite pi manifold A(c of lR? called the normal manifold of
C; and the normal map Ac : lR? lR? induced by (A, C), which is pi with
respect to A(c. [14, Thm. 4.3] shows that Ac is homeomorphic if and only if
it is coherently oriented.
We show that A(c has branching number less than or equal to 4, hence
Robinson's result is actually a corollary of Kuhn and L5wen's.
Key Words
Piecewise linear, piecewise affine, branching number, normal map, pi-normal,
normal manifold, homeomorphism, coherently oriented
Abbreviated Title
On Branching Numbers of Afc.
1			Introduction
Kuhn and L5wen [81 and Robinson [14] have provided deep and elegant results
that characterize the homeomorphic members of certain classes of piecewise
linear (pi) mappings. The purpose of this paper is to show that the class
of mappings examined by Robinson is contained in the class of mappings
examined by Kuhn and L5wen.
Let M be a finite piecewise linear (pi) manifold of lR?, and P : 1R? JRfl
be pi with respect to M, i.e. P is affine on each set in M. The branching
nnmber of M, Kuhn and L5wen [8], is the maximum number of sets in M that
can contain any common face of codimension 2. [8, Thm. 5.3] shows that if
M has branching number less than or equal to 4, then P is a homeomorphism
if and only if it is coherently oriented, i.e. the determinants of P on each set
in M have the same nouzero sign.
Let C be a nonempty polyhedral convex set in real n-dimensional space,
IR?, and A belong to the space of real n x n matrices, IRnxn Robinson
[14] defines a finite pi manifold A(c of lR? [14, Prop. 2.4] called the normal
manifold of C; and the normat map Ac : lR? lR? induced by (A, C), which
is pi with respect to A(c [14, Prop. 2.5]. The main result [14, Thm. 4.3] shows
that Ac is homeomorphic if and only if it is coherently oriented; see Ralph
[10] for an alternative proof, and Robinson [15] for a much simpler proof in
the special case that A is symmetric. It is pointed out in [14, 1] that if
A(c could be shown to have branching number less than or equal to 4, then
[14, Thm. 4.3] would follow from [8, Thm. 5.3]. Indeed, showing that normal
manifolds have this branching number property is precisely our goal.
Throughout the paper, C and A will be as above. Let rc be the Euclidean
projection onto C, that is rc maps each point of 1R? to its nearest point in
C with respect to the Euclidean norm. The identity in JRflXfl is I.
Definition 1 [14] The normal mapping induced by (A, C) is the mapping
from 1R? to 1R? given by
def
Ac = Arc+I--Hrc.
Such normal mappings are called pl-normal mappings.
Pl-normal systems are important in many optimization and equilibrium
problems. They arise directly from variational inequalities or, equivalently,
generalized equations specified by linear mappings and polyhedral convex
sets; and indirectly as approximations to such systems specified by smooth
nonlinear functions over polyhedral convex sets. For example, see Robinson
[16], Ralph [11]. Perhaps the best known of these problems is the linear
complementarity problem [3, 9] which can be posed as a pl-normal equation
Ac(x) = a, for appropriate A E lRflXfl and a ? `Rfl, by taking C to be the
nonnegative orthant 1R?+.
The question of necessary and sufficient conditions for pl mappings to
be homeomorphic was answered for the linear complementarity problem by
Samelson, Thrall and Wesler [18], and later by Murty [9]. Other work on the
general question includes Fujisawa and Kuh [6], Rheinboldt and Vandergraft
[12], Kojima and Saigal [7], Schramm [19], and Eaves and Rothblum [5].
The remainder of this section will be spent giving rigor to our introduc-
tory remarks on pl manifolds, branching numbers, coherent orientation, and
2
homeomorphism results. 2 contains the main result on branching numbers,
Proposition 12.
We recall the following terms.
o+ A set in JRfl is polyhedral convex if it is the intersection of finitely many
closed half-spaces.
o+ A face of a convex set D c IR? is a subset F of D such that for
x1,x2 E D and 0 < t < 1, if tx1 + (1 --H t)x2 belongs to F then x1,x2
belong to F.
Definition 2
1. An n-cell [4], or chamber [8], (in JRfl) is a polyhedral convex set with
nonempty interior in 1R?
2. A pl manifold, or chamber system [8], of lR? is a locally finite family of
n-cells covering JRfl, any two of which intersect in a (possibly empty)
common face. A pi manifold of IR? is finite if it consists of finitely
many n-cells.
3. Let M be a pi manifold of IR?. The branching number [8] of M is the
least b E ?1, 2,... , oo] such that every face of an n-cell of M which
has codimension 2 is contained in at most b n-cells.
We note that, according to the proof of [14, Prop. 2.4], any pI manifold M
of 1R? is also a subdivided pi manifold of dimension n in the sense of Eaves [4];
namely, in addition to satisfying the requirements of Definition 2.2, it has
the property that each face of dimension n --H 1 of an n-cell of M is contained
in at most two n-cells of M.
3
Definition 3 Let P : JRfl			1R?, and M be a pi manifold of 1R?
1. P is pi with respect to M if for each a E M, there are Ag E iRflXfl
and bg C iR? such that
P(x) = Agx + b0, Vx E a.
2. If P pi with respect to M and the matrices Ag (a E M) are as above,
the determinants of P are the determinants of the matrices Ag.
Suppose P, M and Ag (a E M) are as in the definition. Note that M is
not uniquely determined by P. The set of matrices fAg a E M) and the
set of their determinants are, however, uniquely determined by P and are
independent of M. Furthermore it is easy to see, since M is locally finite,
that P is not only continuous but locally Lipschitz; and that P is a Lipschitz
mapping if M is finite.
We now present the characterization theorems of Kuhn and L5wen [8],
and Robinson [14], respectively.
Theorem 4 Suppose M is a finite pi manifold of 1R? with branching number
tess than or equal to ?. If P : iR? iR? is pi with respect to M, then it is a
homeomorphism if and only if it is coherently oriented.
Proof Let P be pi with respect to M. [8, Thm. 5.3] says that if P is proper,
i.e. P-1(D) is compact for any compact set D C IRn, then it is bijective if
and only if it is coherently oriented.
Suppose P is bijective. It is easy to see that P(M) ffi?ef fP(a) a E MJ is
a pi manifold of IR?, and that P-1 is pi with respect to P(M). Hence both
4
P and P-1 are continuous, and P is a homeomorphism. To conclude, we
note that each of the conditions of bijectivity and coherent orientation imply
that P is invertible on each of its n-cells, from which it follows, by finiteness
of M, that P is proper.			0
Theorem 5 Ac is a homeomorphism if and onty if Ac is coherently or:-
ented.
Proof According to [14, Thm. 4.3], Ac is a Lipschitzian homeomorphism if
and only if Ac is coherently oriented. Now Ac is pl with respect to the finite
pi manifold A(c [14, Thm. 2.5(i)] hence, as noted previously, Ac is Lipschitz,
and the stated result follows.			0
Details of A(c will be given in 2. It follows from our main result, Proposi-
tion 12, that the branching number of A(c is less than or equal to 4, hence
we can apply Theorem 4 directly to the pi-normal mapping Ac to obtain
Theorem 5.
2 Normal manifolds, their quotients and lo-
cal structure
Further notation:
o+ The relative interior of a set F in IR? is denoted ri F. A basic fact
[17, Thm. 6.1] is that each nonempty convex set in JRfl has nonempty
relative interior.
o+ The affine hull of a set F c 1R? is denoted aff F. The linear subspace
parallel to aff F is denoted par F. The linear subpace parallel to the
largest affine subspace of F is denoted lin F.
5
o+ A set Kin JRfl is a cone if for each a>O and k E K, ak E K. If K is
nonempty cone, the polar cone of K is
Ko%?effxEIRnI (x,k)<?QVkEKJ.
The polar cone of the empty set is defined to be the empty set.
o+ The normal cone to C at c E C is
Nc(c?d=effvEIRnI (v,c--Hc?<Q VcECJ.
Nc(c) is defined to be the empty set if c ?
The tangent cone to C at c E `Rfl, is Tc(c) d4 Nc(c)0.
o+ If X is a nonempty set in IR?, X1 is the set of vectors z C lR? such
that (z,x) = 0 for each x E X.
o+ The critical cone [13j to C at x E-IR? is Tc(rc(x)) n [x --H rc(x)]1.
By convention, the sum or cartesian product of two sets in IR?, one of which
is empty, is also empty.
Proposition 6 [14, Prop. 2.1, 2.4, 2.5]
1. For each face F of C and each point f in the relative interior of F,
the normal cone to C at f is the same (nonempty) set. Denote this by
NF. Also, for any point c E F,
N?=Nc(c)fl(F--Hc)1.
6
2. The family of sets F + NF, where F is any nonempty face of C, is a
pi manifold of 1R?.
3. On each n-cell F + NF, where F is a nonempty face of C, Ac acts as
an affine mapping:
Ac(f+v) = Af +i', Vf E F, v E NF.
The constancy of Nc(x) for x in the relative interior of a face F of C is also
shown by Burke and More' (2, Thm. 2.3j.
Definition 7
1. Let F be a nonempty face of C and f E ri F. The normal cone of C on
F (in IR?) is NF d=ef Nc(f).
2. The normal manifold [14] of C (in IR?), denoted Arc, is the family of
sets F + NF where F is a nonempty face of C.
Since C is polyhedral convex, it has finitely many nonempty faces F (see [17,
Thm. 19.1]). So part 2 of Proposition 6 says that Arc is a finite pl manifold
of IR?. Part 3 says that Ac is pl with respect to Arc.
Our first task is to show one-to-one correspondence between the nonemp-
ty faces of C and n-cdls of Arc.
Proposition 8
1. Let F be a nonempty face of C.
The mappingx . (rc(x),x--Hrc(x)), wherex E F+NF, is a bijection
from F + NF to F x NF.
7
2. The mapping F :. F + NF is a bijection from the family of nonempty
facesF ofC toA(c.
Proof
1. Let ?(x) def (rc(x), x --H irc(x)). Clearly the addition mapping + is the
inverse of ?. Also + : F x NF H F + NF. So we only have to show
I(F+NF) cFx NF.
Let fE F, v E NF. Then v E Nc(f) by Proposition 6.1. So f+v E
(I + Nc)(f) hence, by [1, Ex. 2.8.2j, f = irc(f + v). So i(f + v) =
(f,v) E F x NF.
2. Suppose F, G are nonempty faces of C such that F + NF = G + NG.
Let f E riF and v E NF. Since f+ v E F+ NF = G+No, we have
from part 1 that f = rc(f + v) E C. So (ri F) n G is nonempty and
it follows, by [17, Thm. 18.1j, that F c G. By symmetry, G c F, i.e.
F =
0
We now consider linear subspaces that are either contained in lin C or
orthogonal to par C, and show how they can be factored out of A(c
Proposition 9 Let L, M be linear s?bspaces of lin C, (parC)' respectively.
1. The mapping F F n L' is a bijection from the faces of C to the
faces of C n L?
8
2. Let ? E C n L1 and m be the dimension of (L + M)1. The mapping
i? (? --H co) n (L + M)1 is a bijection from the n-cells g ofA(c to the
m-cells of the normal manifold of (C --H co) fl L in (L + M)1
Proof
1. Note that, since L is parallel to an affine subspace of C,
C = (C n L) + L;
in particular (C n L) # ?. Let F be a face of C. If F n L1 is
nonempty, let ci and c2 belong to C n L1, and t E (0,1) be such that
tc1 + (1 --H t)c2 E F A L?. Then c1,c2 E F AL1 because F is a face
and L' is convex, that is F A L1 is a face of C A L'. So the mapping
F FAL1 from the faces F of C to the faces of CAL is well defined.
For injectivity, suppose F and F' are faces of C such that F A L --H
F'AL?. Without loss of generality assume that F and F' are nonempty.
NowC=(CAL1)+LhenceforanyfEFCC,f+LCC.LetlEL,
then (1/2)(f--Hl)+(l/2)(f+l) E F,sof+lE F. Hencef+LCF,
i.e. L is parallel to an affine subspace of F, and F = (F A L1) + L.
Likewise L is parallel to an affine subspace of F', hence
F'= (F'AL1)+L=(FAL1)+L=F.
For surjectivity, let G be a nonempty face of C A L1. Since G c L'
we have (G+L)AL1 --H G It is left to show that G+L isafaceofC.
9
NowG+LCCbecauseGCCflLand(CflL1)+L=C.Suppose
c1,c2 E C, t E (0,1) and c d4 tc1 + (1 --H t)c2 E G+ L. For i = 1,2
we can decompose cj as the sum ii + Zj where i? E L and Zj E C n L.
As c E G+L and G c L, we must havetz1 +(1 --Ht)z2 E G. Thus
z1,z2 E G, G being aface of Cfl L, and c1,c2 E G+L.
2. We use Proposition 8.2 and part 1 above. Recall that Co belongs to
C n L', and let ?0 d=ef C --H co Note that part 1 applies when C is
replaced by C0, and we have
C0nL' c parCflL1
c M1nL1=(L+M)1.
Now consider the following mapping from A(c to the normal manifold
of C0 n L1 in (L + M)1: given ? E ?c, take the unique face F of C
map Gto the face G0 %?ef G--Hco of(F--Hco)flL1, and finally map G0
to the sum of G0 and the normal cone, in (L + M)1, of C0 n L' on
G0. This mapping is well defined and, as the composition of bijective
mappings, is itself bijective. Therefore, any surjective mapping from
(the finite set) A(c to the normal manifold of C0nL1 in (L+M)1 must
be bijective.
Let F be a face of C,soF0 %?ef F - Co is a face of C0 and F0 n L1isa
face of C0 A L1. Since F = (F A L') + L, [16, Thm. 6.7] yields
riF = ri(FflL1) +riL = ri(FflL1) +L,
10
and, in particular, ri F contains ri(F fl L). Choose go E ri(Fo n L1),
so go + Co E ri(F n L1) and, by Proposition 6.1,
NF = Nc(go + co) = NcnLi(go + co) n L1 = Nc0n?i(go) n L1,
where the second equality follows from the identity C = (C n L1) + L.
Also F0 = (F0 n L1) + L, so we have
[F+NF--Hco]fl(L+M)'
= [F0nL' + L + NconL(go)flL1]fl(L?flM')
= [F0nL1 + NconL(go)flL']flM?,
= F0 n L' + [Nc0n?i(go) n L' n M?j, since F0 n L? c M
= F0 n L' + [NconLi(g0) n (L + M)1J.
We already know that F0 n L' is a face of C0n L'. Moreover, by choice
of the go, NconLi(go) n (L + M)' is the normal cone, in (L + M)', of
Co fl L1 on F0 n L?.
We have shown that a i,' (a --H CO) n (L + M)? defines a mapping from
the n-cells a of ATe to the m-cells of the normal manifold of Co fl L1
in (L + M)1; and that, given part 1, this mapping is surjective. The
proof is complete.
0
When 0 E C, i.e. lin C is the largest subspace contained in C, part 2 of the
last proposition suggests the idea of a quotient of a normal manifold.
11
Definition 10 Let L, M be linear snbspaces ofC, (par C)1 respectively. The
quotient of A(c over L + M, denoted A(c/(L + M), is the normal manifold
ofCflL' in(L+M)1.
This can easily be extended to the situation in which L is a subspace of
lin U but not of C. We will not need such generality for our investigation of
branching numbers, however.
Next we examine the local structure of A(c.
Proposition 11 Let x C JRfl, and K be the critical cone to C at x.
1. The mapping F i' TF(lrc(x)) is a bijection from the faces F of C such
that x E F + NF, to the nonempty faces of K.
2. The mapping ? :, T?(x) is bijection from the n-cells ofA(c that contain
x to the n-cells ofA(K.
Proof
1. Let c <? rc(x) and ? %ef --H irc(x). Let ?(x) be the family of faces F
of C such that x E F + NF. Observe that for each face F of C we have
F = (affF) fl C: F c (affF) fl C, and for any x E (aff F) n c, take
f E ri F and observe for sufficiently small t > 0 that (1 --H t)f + tx E F,
hence x ? F. Note that each F E ?(x) is polyhedral convex because
C is polyhedral convex. We will also use the fact that for a polyhedral
convex set D and each d E D, TD(d) = cone(D --H d), where for any
nonemptyset Sc JRfl, cone(S) d4 ?asIa>O, 5 E 5).
12
Let F E ?(x); by Proposition 8.1, c E F and v E NF. We will show
that G def TF(c) is a face of K. By Proposition 6.1, NF c (F --H
hence F --H c C v'. In particular,
G = cone(F --H c) c [cone(C --H c)J n v1 =
Next suppose k1,k2 E K and t E (0,1) are such that k %?ef tk1 + (1 --H
t)k2 E G. Choose a> 0 small enough such that
c+ak1,c+ak2 E C,
c+ak E F.
Since c + ak equals t(c + aki) + (1 --H t)(c + ak2) and F is a face of C,
we see that ak1,ak2 E (F --H c). Therefore k1,k2 E G, and G is a face
of K. We have shown that the mapping F i? TF(c) from ?(x) to the
nonempty faces of K is well defined.
For injectivity, suppose TF(c) = T?i(c) where F, F' E ?(x). So for
each f E F there is a E (0,1) such that a(f --H c) E F' --H c, hence
(1 --H a)c + af c F'. As F' is a face of C, f c F', i.e. F C F'. By
symmetry, F D F', and F =
For surjectivity, let G be a nonempty face of K. Since K is a cone, G
is a cone too. Let F %ef (G + c) fl C. As G + c and C are polyhedral
convex sets containing e, we can decompose the tangent cone of F at
= [cone 0] fl [cone(C --H c)j = 0 fl Tc(c).
Therefore T?(c) = 0, so it is only left to be shown that F E ?(x).
13
def
First we note that K= Tp(c), where F = Cn(c+v1): CE F and
Tp(c) = cone[(C --H c) fl vJ = [cone(C --H c)j fl v = K
Second,asGisafaceofTp(c?,(G+c?flfrisafaceoft:lifi,f?EF
and t E (0,1) are such that f def tf1 + (1 --H t)f2 E (G+ c) fl P, then
fi--Hc?f2--HcET?(c?,and?A--H?)+(1--Ht)(f2--Hc?equalsf--HcEG.
Sof?,I2 E (G+e)nF.
Third, (G+c)nP =F: since Gfl(C--Hc) c G c K c v, we get
F = (&+c? flC = (G+c?nCfl(c+v?) = (G+c? flF.
Fourth, we show P is a face of C, for then F, which we have shown
is a face of P, must also be a face of C. Recall that, by construction,
z' E Nc(?). Letc1,c2 E C,tE (Q1),cd4t4+(1?tfr2 E Pandassume
ci ? P. Then (c1--H?,? <0 and, as (c--Hc%v) = 0, (c2--Hc%v) >0
which contradicts ? E Nc(c). So P is a face of C as needed.
It only remains to be seen that x E F + NF. We already know that x =
e+v,wherec?FandF--HccP--Hcci'. ThusvE(F--Hc?1flNc(c?,
and Proposition 6.1 assures us that v E NF.
2. The proof proceeds in a fashion similar to the proof of Proposition 9.2.
We will use the proof of part 1 without reference.
Denote by A(c(x) the family of n-cells of A(c that contain x. Let ? E
Wc(x) and, using Proposition 8.2, F be the unique face of C such that
14
= F + NF. Then c E F and G def TF(c) is a face of K. The mapping
of ? to the sum of G and the normal cone to K on G therefore defines
a function from A(c(x) to AfK. This function is the composition of
invertible mappings, hence is invertible. It follows that any surjective
mapping from A(c(x) to A(K is bijective.
Let a and F be as above, so c E F and v E NF. Consider
= cone[(F --H c) + (NF --H v)j
= cone(F --H c) + con?N? --H v)
since F --H c, NF --H v are polyhedral convex and contain zero. Also, as
NF is a cone containing v, cone(N? --H v) equals NF + span(v), where
span(v) <Lef t?vIa E IRJ. So
= T?(c) + NF + span(v).
Recall that TF(c) is face of K, and, by definition K --H Tc(c) fl v1. Let
N be the normal cone to K on TF(c). By Proposition 6.1,
N = NK(O)fl[TF(c)--HO]1
= [Tc(c) fl v1]0 fl [cone(F --H c)j1
= [Nc(c) + span(v)J n [F --H c11,
since Tc(c) and v1 are polyhedral convex cones, and (v1)0 --H span(v).
Now v E NF c (F --H c?1, so span(v) c (F --H c)1 and we get
N = [Nc(c) n (F --H e)1J + span(v) = NF + span(v),
15
where the second equality follows from Proposition 6.1. We deduce
that ? T0(x) defines a mapping from the n-cells (7 of A(c(x) to the
n-cells of )\(?; and, given part 1, that this mapping is a surjection.
Hence the mapping is bijective.
u
We have arrived at our main result.
Proposition 12 Suppose G is a nonempty face of F + NF of codimension
m, where F is a face of C. Let x E ri G and K be the critical cone to C at
def			def --H
x.			Define c =			v = x
L d4 par[(G--Hv)flF], M def par?G--Hc?flN?].
Then L c K, M c K1, L+M = parG, and there is a one-to-one correspon-
dence between the n-celis ofA(c containing x and the m-cells of?K/(L+M).
Proof If L c K, M c K', and L + M = parG, then the dimension of
(L + M)1 is m, and the bijective correspondence between the n-cells of A(c
containing x and the m-cells of A(K/(L + M) follows from Propositions 11.2
and 9.2.
We will show
G=kG--Hv)nF]+kG--Hc?flN?].			(1)
Let c+ v E 0 where c E F and v E NF, then c+ Qc+ v E F+ NF and, by
convexity of 0,
= (1/2)(c+v)+(1/2)(c+v) E 0.
16
So c + v and e +`, belong to G, and it follows that c + v lies in j(G --H v) fl
Fi+kG--Hc)flN?]. ConverselyifcE (C--Hv)flF and vE (G--Hc?flNF,
then both c + v and c + v belong to G, and an &gument similar to the one
above yields c + v E G.
Recall (Proposition 6.1) that NF = Nc(c) n (F --H c), so par F and
par NF are orthogonal. Hence the decomposition of x as the sum c + v,
where c E (G --H t') n F and v E (G --H c) n NF, implies c and v are unique,
thus c = c and v = v. Using (1) and [17, Thm. 6.7], we can express riG is
the sum of ri[(G --H v) n F] and ri[(G --H c) fl NF]. As x E ri G it now follows
that c and v are relative interior points of (G --H v) n F and (G --H c) fl NF,
respectively.
Therefore we have, in the notation of the previous proof,
L = cone([(G --H v) fl Fj --H c),			(2)
so L C cone(C --H c) = Tc(c). Also v belongs to NF (Proposition 8.1) hence
to (F --H c)', therefore v1 ? cone(F --H e) ? L. This shows that the critical
cone K d4 Tc(c) fl v1 contains L. Similarly,
M=con?[(&--Hc)flN?j--Hv),			(3)
so M C cone(N? --H t'). For v E NF C Nc(c) and d E (C --H c) fl v1,
(v --H v,d) = (v,d) <0, hence
con?N? --H v) c [cone(C --H c) fl v1]0 = K0.
Thus the linear space M lies in K0, which shows it is a subspace of K'.
17
It only remains to be seen that par G = L + M. This follows from (1),
(2), and (3), given that for any nonempty sets A and B in lR?, par(A + B) =
par A + par B. The easy proof of the last fact is left to the reader. 0
Corollary 13 A(c has branching number less than or equal to 4. In partic-
ular, Ac is pi with respect to a finite pi manifold of Iftfl that has branching
number less than or equal to 4.
Proof If n = 1 then, using the convention that the empty set has dimension
-1, the only face of C of codimension 2 is the empty set. Trivially, A(c has
cardinality of 3 or less, hence its branching number is less than or equal to
3. (Alternatively, one could ignore the empty set and argue that the idea of
branching numbers is vacuous.)
Let n > 2 and suppose G is a (nonempty) face of F + NF of codimension
2, where F is a (nonempty) face of C. Let x, K, L and M be as in Proposi-
tion 12. The proposition says that L + M has codimension 2, and that the
number of n-cells of A(c containing G (which contains x) is not greater than
the number of 2-cells of A(K/(L + M).
Consider A(K/(L + M) which is the normal manifold of a nonempty poly-
hedral convex cone in a 2-dimensional space. The maximum number of 2-cells
of A(K/(L + M) is four: it consists of one 2-cell if K n L1 is fOJ or (L + M)i,
two if K n L? is a ray or a halfspace, and four otherwise.
El
Therefore Robinson's homeomorphism result, Theorem 5, is a corollary of
Kuhn and L5wen's homeomorphism result, Theorem 4.
18
A minor point is that for a finite pi manifold M of IR and a mapping
P : IR JR that is pi with respect to M, it is almost trivial that P is a
homeomorphism if and only if it is both proper and coherently oriented. In
other words the branching number of M, which equals the cardinality of M
if the empty set is assigned codimension of 2, has no bearing on whether or
not P is a homeomorphism. However, as Kuhn and L5wen [8, p. 122] note,
in all higher dimensions the upper bound of 4 on the branching number is
tight: there are coherently oriented maps that are pi with respect to finite pi
manifolds of branching number 5, but that are not homeomorphic.
Acknowledgement
I am grateful to Stephen M. Robinson for comments including a simpler proof
of Proposition 8.1, and mention of the references [3] and [13].
References
[1] Brez'is, H. (1973). Operateurs Maximaux Monotones et Semi-groupes de
Contractions dans les Espaces de Hilbert. North-Holland Mathematics
Studies No. 5, North-Holland, Amsterdam.
[2] Burke, J.V., and More', J.J. (1988). On the Identification of Active Con-
straints. SlAM J. Numer. Anal. 25 1197-1211.
[3] Cottle, R.C., Pang, J.S., and Stone, R.E. (1992). The Linear Cornpie-
mentarity Problem. Academic Press, Boston.
[4] Eaves, B.C. (1976). A Short Course in Solving Equations with PL Hom?
topies. In: R.W. Cottle and C.E. Lemke, eds., Nonlinear Programming
19
(SIAM-AMS Proceedings, v. 973-143). American Mathematical Society,
Providence, RI.
[5] Eaves, B.C., and Rothblum, U.G. (1990). Relationships of Properties of
Piecewise Affine Maps over Ordered Fields. Linear Algebra Appi. 132
1-63.
[6] Fujisawa, T., and Kuh, E.S. (1972). Piecewise-Linear Theory of Resistive
Networks. SlAM J. Applied Math. 22 307-328.
[7] Kojima M., and Saigal, R. (1980). On the Relationship between Condi-
tions that Insure a PL Mapping is a Homeomorphism. Math. Operations
Res. 5 101-109.
[8] Kuhn, D., and L5wen, R. (1987). Piecewise Affine Bijections of IR?, and
the Equation 5x+ --H Tx- = y. Linear Algebra Appl. 96 109-129.
[9] Murty, K.G. (1972). On the Number of Solutions of the Complementar-
ity Problem and Spanning Properties of Cones. Linear Algebra Appl. 5
65-108.
[10] Ralph, D. (1990). A New Proof of Robinson's Homeomorphism Theorem
for Piecewise Linear Maps. Ch. 4 in Rank-i Support Functionals and
the Rank-i Generalized Jacobian, Piecewise Linear Homeomorphisms.
Ph.D. Thesis, Computer Sciences Technical Report #938, Computer
Sciences Dept., Univ. of Wisconsin, Madison, WI. To appear in Linear
Algebra Appi.
[11] Ralph, D. (1990). Global Convergence of Damped Newton's Method for
Nonsmooth Equations, via the Path Search. Technical Report TR 90-
20
1181, Dept. of Computer Science, Cornell Univ., Ithaca, NY. To appear
in Math. Operations Res.
[12] Rheinboldt, W.C., and Vandergraft, J.S. (1975). On Piecewise Affine
Mappings in IR?. SlAM J. Applied Math. 29 680-689.
[13] Robinson, S.M. (1987). Local Structure of Feasible Sets in Nonlinear
Programming, Part III: Stability and Sensitivity. Math Prog. Study 30
45-66.
[14] Robinson, S.M. (1990). Normal Maps Induced by Linear Transforma-
tions. Manuscript, Dept. of Industrial Engineering, Univ. of Wisconsin,
Madison, WI. To appear in Math. Operations Res.
[15] Robinson, S.M. (1992). Nonsingularity and Symmetry for Linear Normal
Maps. Manuscript, Dept. of Industrial Engineering, Univ. of Wisconsin,
Madison, WI.
[16] Robinson, S.M. (1991). An Implicit Function Theorem for a Class of
Nonsmooth Functions. Math. Operations Res. 16 292-309.
[17] Rockafellar, R.T. (1970). Convex Analysis. Princeton University Press,
Princeton, NJ.
[18] Samelson, II., Thrall, R.M., and Wesler, 0. (1958). A Partition Theorem
for Euclidean fl-space. Proc. Amer. Math. Soc. 9 805-807.
[19] Schramm, R. (1980). On Piecewise Linear Functions and Piecewise Lin-
ear Equations. Math. Operations Res. 5 510-522.
21
