© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Re v.Acad .Canar .Cienc . , VIII (Núm. 1), 93-1 0 0 ( 1996 )
A Practica! Criterion for Multivariate Majorization
Alberto Borobia 1
ABSTRACT: Let X and Y be real nxm matrices: Does there exist sorne
stochastic nxn matrix S such that SX=Y? Does there exist sorne doubly
stochastic nxn matrix D such that DX=Y? We deve/op a practica/ criterion
for so/ving these prob/ems. Moreover, we show how to obtain concrete
matrices S and D when they there exist.
lntroduction
A real square matrix such that the sum of the entries in each column
is equal to 1 is said to be weakly stochastic. A weakly stochastic matrix
with nonnegative entries is said to be stochastic. A matrix is said to be
doubly stochastic if it and its transpose are both stochastic. ·
The problem we are concemed with is the following:
Let X and Y be real nxm matrices: Does there exist sorne stochastk nxn
matrix S such thai SX=Y? Does there exist sorne doubly stochastic nxn matrix
D such that DX=Y?
If a method is given to solve the stochastic case for sorne m, then we
can apply it to solve the doubly stochastic case for m - l. The reason is
that an nxn stochastic matrix A is doubly stochastic if and only if Ae=e
where e denotes the n-dimensional real vector with a11 its components equal
to l. Let X and· Y be two real nx(m -1) matrices and let X'=(X,e) and
l. Parúally supponed by DOI~ PB94·136S·al3·02.
93
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Y'=(Y,e) be the real nxm matrices obtained by adding the vector e as a new
column in X and· Y. Then A is a doubly stochastic matrix such that AX=Y if
and only if A is a stochastic matrix such that AX'=Y'.
This problem has been considered frequently on the literature. We
start a short history by mentioning the classical paper by Hardy,
Littlewood, and Pólya [4] who nicely solved the case m=l for doubly
stochastic matrices. Hom [5] gave a necessary condition in the case m=2
for doubly stochastic matrices, and Sherman [9] proved that it was also a
sufficient condition. The book by Marshall and Olkin [7] is a basic
reference for the theory of majorization; Theorem 15.C.3 in that book gives
a necessary condition (involving convex functions) for any m for doubly
stochastic matrices, and Komiya [6] showed that it was also sufficient. See
also Alberti and Uhlmann [1]. Komiya's paper also contains another
necessary and sufficient condition involving the inner product of matrices.
Ruch, Schranner, and Seligman [8] obtain a practical criterion in the case
m=2 for stochastic matrices; it implies Hardy, Littlewood, and Pólya
result. Recently, a paper by Dress, Ruch, and Triesch [2] develops a
cohomology theory for fans (that is, stratifications of R0 by closed convex
eones) that implies a geometric interpretation of earlier work by Hardy,
Littlewood, and Pólya, as well as by Ruch, Schranner, and Seligman.
There does not seem to be a practical algorithm to solve the problem
in the case m~3 for stochastic matrices and in the case m~ for doubly
stochastic matrices. The purpose of this paper is to develop such an
algorithrn. Moreover, it will be possible to obtain concrete solutions when
they exist.
94
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
2. .lf:nf (X,Y), 'WJn( X,Y), and Jn(X ,Y)
By <xºl, ... ,x<•»~n we denote the span of (x<l), ... ,x<•l¡dRn. We
will write the standard basis of IRn as ( e<1>, .•. ,e<nl}. For the real nxm
matrix A we will employ either the notation A=(a(l), ... ,a<m» where
a<il=(aui, ... ,aül)1 for each j=l, ... ,m or A~(a<i» where a?l denotes the
1 n 1 1
entry in the z.tlt row and the l column.
Let X=(x<1i, ... ,x<ml) and Y=(y(l), ... ,/ml) be real nxm matrices. The
set of all real nxn matrices A such that AX=Y (or, equivalently, such that
Ax<il=y<il for each j=l, ... ,m) will be denoted by .lf:f(X,Y). The following
n
result is trivial,
Lemma 1: Let X=(x(l), ... ,x<ml) and Y=(/1l, ... ,/ml) be real n><m
matrices. Then .lf:f(X,Y) is not empty if and only if n
m .
L ')...j'> = O for ')... , ... ,/... elR
1 1 m
i =l
m
L/....i> =o.
i=l 1
Given two real nxm matrices X=(x(l>, ... ,x<m» and Y=(y(l>, ... ,/ml),
consider the following algorithm:
1: i=O, S=0dRn, /=0c{l, ... ,m}.
2: i=i+ l. If i>m then stop. Otherwise
3: If x<ilt.<S> then S=Su(x<i>¡, /=/u(i} and go to 2.
If x<ile<S> obtain the unique decomposition x<il= L /....xm. Then:
je/ J
If /il= L ')... ./") then go to 2 .
. je/ J
If i>'*- L ')... .Y(J) then '.lf:f(X,Y)=0' and stop.
je/ J n
95
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
The result of the algorithm is:
- either Af(X,Y)=0, and in this ca8e there is nothing more to study;
n
• - .1 .r • (il) <i'> . - or we obtam /"-(1 , ... ,1 )!:;(l, ... ,m) w1th (x , ... ,x ) a !mear
independent set in Rn and
.1 r
In this case if we consider the real nxr matrices X'=(x<• >, ... ,x<i 1) and
.1 .r
Y'=(/' >, ... ,/' 1) then Af(X,Y)=Af(X',Y').
n n
We recall that a real nxn matrix A=(a~1) is weakly stochastic if and
1
onl yi f 1,. or each 1'=l , ... ,n we h ave a1u +iau2 i+ ... +anu =i1 . we g1· ve ano the r
well known characterization: A real nxn matrix A is weakly stochastic if
and only if f or ea ch xe Rn the sum of the components of x is equal to the
sum of the components of Ax.
Given the real nxm matrices X and Y, let 'IPJ'(X,Y) denote the set of - n
ali weakly stochastic nxn matrices A such that AX=Y, and let J'(X,Y) denote
n
the set of ali stochastic nxn matrices A such that AX=Y. Clearly,
Jn'( X,Y) e 'IPJn'( X,Y) e Afn( X,Y).
Our principal purpose is to be able to determine if J'(X,Y) contains sorne
n
element and, if J'(X,Y)~. to obtain sorne matrix in J(X,Y). If we first
n n
apply to X and Y the algorithm given above, then we need to study what
happens only in the case where X and Y are real nxm matrices with rank of X
equal to m.
The next result follows from the characterization of weakly stochastic
matrices given above.
96
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Lemma 2: Let X=(x(l'. ... ,x<m>) and Y=(/1>, ... ,y<m>) be real nxm
matrices with rank X=m. Then 'WJ(X,Y) is not empty if and only if
n
n n
:E x(J) = :E /il for each j=l, ... ,m.
i= 1 i i=l ¡
If 'W~(X,Y)=0 then there is nothing more to study. Therefore, from now
on we will suppose that X=(x(l),. .. ,x<m» and Y=(/1>,. . .,/m» are real
n n
nxm matrices with rank X=m and such that :E x~)= :E y~) for each
i=l i= 1
j=l,. . .,m. Moreover, up to reordering of coordinates, we will suppose that
we can extend the linearly independent set (x0 >, ..• ,x<ml} to a basis of R0
by means of the additional vectors ( e(l), .. .,e<n-m)}. Therefore, for each
j=n-m+l,. . .,n we obtain a unique decomposition of e(J) given by
For each k=l,. . .,n-m let aet.> be any n-dimensional real vector with
n .
:E a¡'>=l. Consider the unique weakly stochastic matrix A=(a~» depending
i=I
on X, Y and ( a(l) ,. • .,a<n-m)} that is defined by
Ax(hl = y(h) for each h=l,. . .,m and
Aeet.> = aet.> for each k=l,. . .,n-m.
Therefore, we obtain for each j=n-m+l,. . .,n
From Lemma 2 and the previous paragraph it follows that a one-to-one
correspondence exists between the set of real (n - l)x(n - m) matrices and
the set 'WJ(X,Y). The real (n - l)x(n - m) matrix Z=(z~)) is associated with
n 1
the nxn matrix A=(a~))e 'WJ(X,Y) where
1 n
97
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
(*) aü>
1
for j=l, ... ,n-m and i=l, ... ,n-1;
n • 1
1 - L z?>
1
i =l
for j=l, ... ,n-m.
(*) a?> =
1
for j=n-m+l, ... ,n and i=l, ... ,n-1;
(*) aU>
n
for j=n-m+l, ... ,n.
It remains to determine if 'fl!J(X,Y) contains sorne nonnegative matrix,
n
that is, if J(X,Y) is nonempty. But this is just the first step of a
n
linear programming problem (l.p.p.). We recall briefly the basic facts of a
l.p.p. (see Hadley [3]): Given a set of r linear inequalities or equations
in s variables, we wish to find nonnegative values of these variables that
satis/y the constraints and maximize or minimize a given linear function
(the objective function) of the variables.
Any nonnegative values that satisfy the constraints are called a
feasible solution; and any feasible solution that optimizes the objective
function is called an optimal feasible solution. The simplex method,
developed by Dantzig in 1947, isthe best-known and most widely-used
procedure for solving a l.p.p.. The first step of the simplex method either
determines the non-existence of feasible solutions or calculates a concrete
feasible solution, and this part of the simplex method is independent of
the objective function. If a feasible solution exists, then the simplex
method either calculate an optimal feasible solution or concludes that the
objective function is unbounded;
98
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Now we can state the criterion,
Theorem: Let X=(x(l', ... ,x<m>) and Y=(y(l>, .. .,y<m>) be real nxm
matrices with rank X=m, with
i x<i> = f. y~> for j=l , .. .,m,
i·= 1 1 i= 1 1
for each j=n-m+J, .. .,m.
Then {,(X,Y) is not empty if and only if there exist nonnegative values
z~~ for j=l, .. .,n-m and i=l, .. .,n-1 satisfying the following linear
inequalities:
(*)
(*)
n • 1 r z~) ~ 1 for j=l, .. .,n-m.
l
i =l
n-m m L a.Ulz(kt <!: _ L r.tú)y(h)
l< i t\ 1
l<= 1 h= 1
for j=n-m+l, .. .,m and i=l, .. .,n-1;
n-1 n-m n-1 m
(*) L L a.~>z¡> ~ 1 - .r L 13~>y;> for j=n-m+l, ... ,n.
i=ll<=l i=lh=l
Note that we have a l.p.p. without objective function. Applying the
first part of the sirnplex rnethod we will obtain either J(X,Y)=0 or sorne
n
concrete rnatrix which belongs to J(X,Y). If we include sorne objective
n
function then the criterion can be used to solve special problerns (note
that {,(X,Y) is always a bounded polytope) such as:
For two given real nxm matrices X and Y, find an Ae {,(X,Y) such that
trace A<!:trace B for ali Be J(X,Y).
n
99
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
References:
[1] Alberti and Uhlmann; Stochasticity and Portia/ Order, Reidel,
Dordrecth, 1982.
[2] Dress, Ruch, and Triesch; Extremals of the Cone of Norms and the
Cohomology of c3-Stratifications, Adv. Appl. Math. 13 (1992), 1-47.
[3] G. Hadley; Linear Programming, Addison-Wesley, Reading;Mass., 1962.[4]
Hardy, Littlewood, and Pólya; Inequalities, Cambridge U.P., New York, 1952.
[5] A Hom; Doubly Stochastic Matrices and the Diagonal of a Rotation
Matrix, Amer. J. Math. 76 (1954), 620-630.
[6] H. Komiya; Necessary and Sufficient Conditions for Multivariate
Majorization, Linear ALgebra Appl. 55 (1983), 147-154.
[7] Marshall and Olkin; Inequalities: Theory of Majorization and Its
Applications, Academic, New York, 1979.
[8] Ruch, Schranner, and Seligman; Generalization of a Theorem by Hardy,
Littlewood, and Pólya, J. Math. Anal. Appl. 76, No.1 (1980).
[9] S. Sherman; Doubly Stochastic Matrices and Complex Vector Spaces, Amer.
J. Math. 77 (1955), 245-246.
Alberto Borobia
Departamento de Matemáticas
Facultad de Ciencias, U.N.E.D.
28040 Madrid, SP AIN
Recibido: 26 Septiembre 1996
100