Digital Signal Processing Reference
In-Depth Information
♠
Theorem 21.8.
Majorization and stochastic matrices.
A
is doubly stochas-
tic if and only if
y
majorizes
Ay
for every real vector
y
.
♦
Theorem 21.9.
Majorization, and existence of a stochastic matrix.
Given
two real vectors
x
and
y
,
we have
y
x
if and only if
x
=
Ay
for some doubly
stochastic matrix
A
.
♠
♦
Theorem21.10.
Majorization and orthostochastic matrices.
Given two real
vectors
x
and
y
,
we have
y
x
if and only if
x
=
Ay
for some orthostochastic
A
.
♠
♦
Example 21.11: T-transforms
A special case of doubly stochastic matrices called
T
-transforms (see p. 21
of Marshall and Olkin [1979]) has considerable importance in the theory of
majorization. A
T
-transform is a matrix of the form
T
=
α
I
+(1
−
α
)
J
,
(21
.
54)
where 0
1,
I
is the identity, and
J
is the identity with
exactly one
pair of columns interchanged.
For example, the
J
matrices
≤
α
≤
⎡
⎤
⎡
⎤
010
100
001
100
001
010
⎣
⎦
⎣
⎦
J
1
=
and
J
2
=
generate, respectively, the
T
-transforms
⎡
⎤
⎡
⎤
α
1
−
α
0
10
0
⎣
⎦
⎣
⎦
.
T
1
=
1
−
αα
0
and
T
2
=
0
α
1
−
α
0
0
1
01
−
αα
From the definition and the above examples it is amply clear that a
T
-
transform is
doubly stochastic
as well as
symmetric
(
T
T
=
T
). Note that
⎡
⎤
⎡
⎤
⎡
⎤
⎡
⎤
x
x
x
2
αx
0
+(1
−
α
)
x
1
x
x
x
2
x
0
αx
1
+(1
⎣
⎦
=
⎣
⎦
⎣
⎦
=
⎣
⎦
.
T
1
αx
1
+(1
−
α
)
x
0
and
T
2
−
α
)
x
2
x
2
αx
2
+(1
−
α
)
x
1
Thus, a
T
-transform operating on a vector simply replaces a pair of com-
ponents
x
k
and
x
m
with their convex combinations
αx
k
+(1
−
α
)
x
m
and
αx
m
+(1
−
α
)
x
k
.
All other components are unchanged.
A beautiful result which historically preceded Theorem 21.9 is the fact that
y
=[
y
0
y
P−
1
]
T
x
P−
1
]
T
y
1
...
majorizes
x
=[
x
0
x
1
...
if and only if
we can go from
y
to
x
by using a sequence of
no more than
(
P
−
1)
T
-transforms
[Marshall and Olkin, 1979], that is,
y
x
if and only if
x
=(
T
1
T
2
...
T
P−
1
)
y
(21
.
55)
Search WWH ::
Custom Search