U n × n unitary, [U T e 1 ] i 6= 0 ∀ i,
L(z) = Ud(U T z)d(U T e 1 ) −1 U H , z ∈ C n ( e T 1 L(z) = z T ), L(x) = L(z) 2 ,
U T x = d(U T e 1 ) −1 d(U T z)U T z, x T = z T L(z) (Gianluca),
L = {L(z) : z ∈ C n } is a commutative matrix algebra, L(x)L(y) = L(L(x) T y ) = L(y)L(x) = L(L(y) T x).
Given z T , the first row of L(z), compute the first row of L(z) 2 , L(z) 4 , L(z) 8 , . . . , L(z) 2k. Cost = one U T transform +kn a.o.+ one U transform.
Given z, the first row of L(z), the eigenvalues λ of L(z) can be computed by performing a U T transform, and the eigenvalues of L(z) s are simply λ s .
Circulant, τ , η and µ matrix algebras are of type L.
Given A n × n and its first row, say [z 1 z 2 · · · z n −1 z n ], one can show that A ∈ L, L = τ, η, µ, iff
a i,j−1 + a i,j+1 = a i−1,j + a i+1,j , 1 ≤ i, j ≤ n, where, for s = 1, . . . , n,
a
s,0= a
0,s= a
s,n+1= a
n+1,s= 0, if L = τ,
a
s,0= a
0,s= a
1,n−s+1, a
s,n+1= a
n+1,s= a
1,s, if L = η, a
s,0= a
0,s= −a
1,n−s+1, a
s,n+1= a
n+1,s= −a
1,s, if L = µ.
Examples. Let us write the 4 × 4 τ, η, µ matrices with first row [0 1 0 1]:
0 1 0 1 1 0 2 0 0 2 0 1 1 0 1 0
,
0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0
,
0 1 0 1 1 0 3 0 0 3 0 1 1 0 1 0
,
Let us write the 5 × 5 τ, η, µ matrices with first row [0 1 0 0 1]:
0 1 0 0 1
1 0 1 1 0
0 1 1 1 0
0 1 1 0 1
1 0 0 1 0
,
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
,
0 1 0 0 1
1 0 1 2 0
0 1 2 1 0
0 2 1 0 1
1 0 0 1 0
.
Stochastic by columns ∩ matrix algebras
3×3 stochastic by columns (symmetric, symmetric and persymmetric) matrices:
M=
a c e
b d f
1 − a − b 1 − c − d 1 − e − f
(M
S=
a b 1 − a − b
b c 1 − b − c
1 − a − b 1 − b − c −1 + a + 2b + c
, M
SP=
a b 1 − a − b
b 1 − 2b b
1 − a − b b a
)
p MS(λ) = (1 − λ)[λ 2 − 2λ(a + b + c − 1) + 3ac − a − 3b 2 + 2b − c], eig = a + b + c − 1 ± √
a 2 + 4b 2 + c 2 + 2ab + 2bc − ac − a − 4b − c + 1 3 × 3 stochastic by columns circulant (symmetric) matrices:
C ∩M =
a 1 − a − b b
b a 1 − a − b
1 − a − b b a
C ∩M
S=
a
1−a2 1−a21−a
2
a
1−a21−a
2 1−a
2
a
p C∩M (λ) = (1 − λ)[λ 2 − λ(3a − 1) + b 3 + a 3 − 3ab(1 − a − b) + (1 − a − b) 3 ]
= (1 − λ)[λ 2 − λ(3a − 1) + 3(a 2 + b 2 − a − b + ab) + 1]
b = 1−a−b ⇒ p C∩MS(λ) = (1−λ)[λ 2 −λ(3a−1)+( 3a − 1
2 ) 2 ] = (1−λ)(λ− 3a − 1 2 ) 2 3 × 3 stochastic by columns tau matrices:
τ ∩ M =
a 0 1 − a
0 1 0
1 − a 0 a
, p
τ∩M(λ) = (1 − λ)[(2a − 1 − λ)(1 − λ)]
3 × 3 stochastic by columns eta matrices:
η ∩ M =
a b 1 − a − b
b 1 − 2b b
1 − a − b b a
= M
SP! p
η∩M(λ) = (1 − λ)[λ
2. . . ]
3 × 3 stochastic by columns mu matrices:
µ ∩ M =
a 0 1 − a
0 1 0
1 − a 0 a
, p
µ∩M(λ) = (1 − λ)[(2a − 1 − λ)(1 − λ)]
4 × 4 stochastic by columns symmetric and persymmetric matrices:
M
SP=
a b c 1 − a − b − c
b d 1 − b − c − d c
c 1 − b − c − d d b
1 − a − b − c c b a
4 × 4 stochastic by columns τ matrices:
M∩τ =
a b −b 1 − a
b a − b 1 − a + b −b
−b 1 − a + b a − b b
1 − a −b b a
, (M∩τ ≥ 0) =
a 0 0 1 − a
0 a 1 − a 0
0 1 − a a 0
1 − a 0 0 a
, λ = 1, 1, 2a−1, 2a−1
M∩η =
a b c 1 − a − b − c
b a 1 − b − c − a c
c 1 − b − c − a a b
1 − a − b − c c b a
, (M∩η ≥ 0) =
λ =
M ∩ µ =
a
a−d2 d−a21 − a
a−d
2
d 1 − d
d−a2d−a
2
1 − d d
a−d21 − a
d−a2 a−d2a
, (M ∩ µ ≥ 0) =
λ =
2 × 2 stochastic by columns matrices:
M =
a b
1 − a 1 − b
, λ = 1, a − b 2 × 2 stochastic by columns circulant matrices:
C ∩ M =
c 1 − c 1 − c c
, λ = 1, 2c − 1
Assuming a, b, c ∈ R, the Frobenius norm of A − X, A ∈ M, X varying in M ∩ C, is minimum for c = a +1−b 2 , i.e. when A and X have the eigenvalues different from 1 equal (a − b = 2c − 1).
Fixed A ∈ M, where M is the set of all non negative stochastic by columns n × n matrices, such that |λ 2 (A)| < 1, there exist X ∈ C ∩ M such that
|λ 2 (A)| ≤ |λ 2 (X)| < 1 ?
Note that the eigenvalues of X are easily computable.
6 × 6 stochastic by columns symmetric and persymmetric matrices:
M
SP=
a b c d e 1 − a − b
−c − d − e
b f g h 1 − b − f
−g − h − e e
c g i 1 − c − g
−i − h − d h d
d h 1 − c − g
−i − h − d i g c
e 1 − b − f
−g − h − e h g f b
1 − a − b
−c − d − e e d c b a
6 × 6 stochastic by columns η matrices:
M∩η =
a b c d e 1 − a − b
−c − d − e
b a + c − e b e −2b − a
−c − e + 1 e
c b a −a − b − c
−d − e + 1 e d
d e −a − b − c
−d − e + 1 a b c
e −2b − a
−c − e + 1 e b a + c − e b
1 − a − b
−c − d − e e d c b a
• 3 × 3 singular stochastic by columns matrices:
a a a
b b b
1 − a − b 1 − a − b 1 − a − b
n
=
a a a
b b b
1 − a − b 1 − a − b 1 − a − b
a a c
b b d
1 − a − b 1 − a − b 1 − c − d
n
=?
• 3 × 3 singular stochastic by columns symmetric and persymmetric matrices:
A =
a 1 − 2a a
1 − 2a −1 + 4a 1 − 2a
a 1 − 2a a
∈ η ! λ = 0, 1, ∈ R
A has rank 1 iff a = 1 3 (in such case λ = 0, 1, 0). A ≥ 0 iff 1 4 ≤ a ≤ 1 2 . A is semi positive definite iff a ≥ 1 3 . A ∈ τ iff a = 1 2 (in such case λ = 1, 0, 1).
A
n=
a
nb
na
n
,
a
nb
n=
2a 1 − 2a
2(1 − 2a) 4a − 1
a
n−1b
n−1EXAMPLE. Let A be the following n × n stochastic by columns matrix
A =
0 b
11 0 b
21 − b
10 1 − b
2b
n−20 1
1 − b
n−20
, b
i∈ [0, 1].
Note that the eigenvalues of A are real (even if A is not hermitian), and in the interval [−1, 1]. They are distinct if b i ∈ (0, 1). Obviously, 1 is eigenvalue.
Moreover, also −1 is eigenvalue (prove it!). The remaining eigenvalues are not known (for generic values of the b j ).
Let C be the space of n × n circulant matrices. Let us compute C A , the minimizer of kA − Xk F , X ∈ C, with the aim to compare its eigenvalues with those of A. Let {J 1 , J 2 , . . . , J n } be a basis of C. Then C A = P n
k=1 α k J k , where Bα = c, B rs = (J r , J s ), c r = (J r , A ), 1 ≤ r, s ≤ n. If J k = J 2 k−1 where
J 2 =
0 1
. ..
1
1 0
then (J r , J s ) = nδ rs , (J 1 , A) = (J r , A ) = 0, r = 3, . . . , n − 1, and (J 2 , A) = 1 + P b j , (J n , A ) = n − 1 − P b j . Thus
C
A=
p q
q p
q . . . . . . p
p q
, p = 1 + P b
jn , q = n − 1 − P b
jn = 1 − p.
The eigenvalues of C A can be easily computed. In fact, recalling that C
A= F d(F C
TAe
1)d(F e
1)
−1F
H, [F ]
ij= 1
√ n ω
n(i−1)(j−1), 1 ≤ i, j ≤ n, ω
n= e
i2πn,
first write the vector √
nF C A T e 1 :
√ nF
0 p 0
· 0 q
= √ n(pF e
2+qF e
n) = √ n(pF +qF
H)e
2, F = F
HQ, Q =
1
1 . . . 1
,
and then observe that the eigenvalues of C A are its entries:
pω n i −1 + (1 − p)ω n i −1 = pω i n −1 + (1 − p)ω n n −i+1 , i = 1, . . . , n.
Note that 1 n ≤ p ≤ n−1 n , and that it is sufficient to study the eigenvalues of C A
for 1 2 ≤ p ≤ n −1 n .
The case p = n −1 n (b j = 1 ∀ j).
In this case the eigenvalues of A are obviously known, they are −1, 0 with algebraic multiplicity n − 2, and 1. The eigenvalues of C A are
n − 1
n ω
ni−1+ 1
n ω
ni−1, i = 1, . . . , n.
(draw them!). They are all inside the set {z : |z| ≤ 1}, except 1 (i = 1) and, for even n, −1 (i − 1 = n 2 ).
The case p = 1 2 (P b j + 1 = n 2 ).
In this case the eigenvalues of A are not known (?, perhaps are known if b j =
1
2 ∀ j, and in other particular cases). The eigenvalues of C A are <(ω n i −1 ) = cos 2π(i−1) n , i = 1, . . . , n. They are all inside the set [−1, 1], except 1 (i = 1) and, for even n, −1 (i − 1 = n 2 ). . . .
RESULT. Let A ∈ C n×n be a stochastic by columns (or by rows) n × n matrix.
So, 1 is eigenvalue of A. Let U be a unitary matrix such that U e i = √ 1 n ee i θ , for some i and θ (i = 1, θ = 0 if U = F ), and set L = {Ud(z)U H : z ∈ C n }.
Note that L is a n-dimensional subspace of C n×n , i.e. there exist J k ∈ L, k = 1, . . . , n, linearly independent such that L = Span {J k }. Let L A be the minimizer of kA − Xk F in L,
L A = U diag ((U H AU ) jj )U H = U d(U T z r A )d(U T v) −1 U H , L A = P n
k=1 α k J k , α = B −1 c, B rs = (J r , J s ), c r = (J r , A) where v is chosen such that (U T v) j 6= 0 ∀ j (v = e 1 if U = F ).
Then L A is stochastic by columns and by rows (SEE the second Theorem in the next pages). In particular, 1 is eigenvalues of L A . All eigenvalues of L A are particular points of the convex set { z zHHAz z : z ∈ C n }. So, when A is normal (hermitian) they are in the minimum polygon (real interval) containing the eigenvalues of A. When alternatively A ≥ 0 (?A k ≥ 0 for some k?) they are in the set {z : |z| ≤ 1} whenever L A ≥ 0, but even in the latter case they can be either inside or outside the minimum polygon containing the eigenvalues of A, SEE the above example (however, if A is also normal, they are inside).
[Question: there are matrices A simultaneously normal, non negative and stochas- tic by columns (or by rows) which are not real symmetric and not in C ? ] Proposition.
If A is a non negative n × n matrix, then its best approximation in C is also non negative. (Proof: We know that C A = P
k α k J k with J k = J 2 k−1 ≥ 0 and α k = n 1 (J k , A). If A is non negative then also α k ≥ 0, so C A ≥ 0).
Question: Given A non negative, is L A non negative for other spaces L ? Is τ A
non negative ? Recall that
τ = {Ud(z)U
H: z ∈ C
n}, U =
r 2
n + 1 sin ijπ
n + 1 , 1 ≤ i, j ≤ n.
Elements of a basis of τ are obtained by choosing J k ∈ τ such that e T 1 J k = e T k , k = 1, . . . , n. They are matrices made up of zeros and ones only. Moreover, for such J k , we have
τ
A= X
k
α
kJ
k, α = B
−1c , B
−1= 1
2n + 2 (3J
1− J
3), c
r= (J
r, A).
[·]. If A is non negative, then c ≥ 0, but B −1 c may have negative entries, but
perhaps τ A is yet non negative (investigate!).
THREE THEOREMS on s-stochastic matrix algebras L and on the best ap- proximation in L of A (each more general than the previous one):
First theorem
Set L = {Ud(x)U H : x ∈ C n } where U is a unitary matrix. Choose v such that [U T v] j 6= 0 ∀ j. Note that the choice v = e 1 works for L = C, τ, η, µ, . . . but not for all low complexity matrix spaces L [. . .].
Then L = {L(z) : z ∈ C n } where we have set L(z) = Ud(U T z)d(U T v) −1 U H . Note that v T L(z) = z T , and that x T L(z) = z T L(x), ∀ x, z ∈ C n . Moreover, L(v) = I.
Observe that if L(e) = we T for some w ∈ C n , then L(z) is z T w-stochastic by columns, i.e.
e T L(z) = z T L(e) = (z T w)e T
[we have observed this first for L = η where w = e, v = e 1 (see previous pages)].
When, in general, L(e) = we T ? Iff v T w = 1 and we T ∈ L. Assume w such that v T w = 1, so w is in particular non null. Then we T ∈ L iff
we T = U
e T w
U H = (e T w)(U e i )(U e i ) H , e T w 6= 0. (∗)
Since U e i 6= 0, the equation (*) times e j , with e j | (Ue i ) H e j 6= 0, implies w = αU e i α 6= 0, and, since (U T v) i 6= 0, v T times the equation (*) implies U e i = βe β 6= 0. Thus w = γe γ 6= 0, and, since v T w = 1, we have γ = vT1 e . So, if L(e) = we T , then v T e must be non zero and w must be equal to v
Te e . Now, provided that v T e 6= 0, the matrix v ee
TTe is in L iff
ee T v T e = U
e
Te v
Te
U H = n
v T e (U e i )(U e i ) H . (∗∗) If U e i = √ 1 n ee i θ , then v T e 6= 0 and (**) holds. So, we have proved the following theorem:
Theorem.
If U e i = √ 1 n ee i θ , then L(e) = ee vTTe . It follows that, for any z ∈ C n , the matrix L(z) is z v
TTe e -stochastic by columns, in particular the best approximation of A in L, L A = L(z A ) = U diag ((U H AU ) jj )U H , is z v
TATe e -stochastic by columns, i.e.
e T L A = z vTATe e e T . Finally note that one of the eigenvalues of L A , (U H AU ) ii , is equal to 1 n e T Ae, and that z v
TATe e = n 1 e T Ae.
[For example, if L = C, η, . . . (where v can be chosen equal to e 1 ), then e T L(z) = z T L(e) = (z T e)e T = (P z i )e T , and e T L A = ( n 1 e T Ae)e T ].
In particular, if A is stochastic by columns (e T A = e T ) or by rows (Ae = e),
then L A is stochastic by columns.
Second theorem
Let U be a n × n unitary matrix, and set L = {Ud(z)U H : z ∈ C n }. Choose v ∈ C n such that (U T v) j 6= 0 ∀ j (v = e 1 if L = C, τ, η, µ, . . .; v ∈ R n whenever possible, f.i. if U ∈ R n ×n ). Then, if we set
L r (z) = U d(U T z)d(U T v) −1 U H (v T L r (z) = z T ), L c (z) = U d(U H v) −1 d(U H z)U H (L c (z)v = z),
L can be also represented as L = {L r (z) : z ∈ C n } = {L c (z) : z ∈ C n }. Note that x T L r (y) = y T L r (x), L c (y)x = L c (x)y, L r (v) = I, L c (v) = I.
Theorem.
If one of the columns of U has all entries equal each other, i.e. ∃ i and θ such that U e i = √ 1 n ee i θ , then
(1) L r (e) = ee eTTv , L c (e) = e ee
TTv (⇒ ee T ∈ L) and therefore L r (z) is e z
TTe v - stochastic by columns, and L c (z) is e z
TTe v -stochastic by rows; in other words, X ∈ L ⇒ X is s X -stochastic by rows and by columns for some s X . [Note that v T e 6= 0 because (v T U ) i 6= 0 ((v T U ) j 6= 0 ∀ j)].
(2) Given A ∈ C n×n , the matrix L A = L r (z r A ) = L c (z c A ) = U diag ((U H AU ) jj )U H , defined as the minimizer on L of kA − Xk F , has (U H AU ) ii = n 1 e T Ae as eigenvalue, and is n 1 e T Ae -stochastic by rows and by columns, i.e. L A e =
1
n (e T Ae)e, e T L A = n 1 (e T Ae)e T .
(3) If A is stochastic by columns or by rows, then L A is stochastic by rows and by columns.
proof. (1): Note that M
j:= U
e
Te
U
H∈ L, ∀ j, M
j= (e
Te )(U e
j)(U e
j)
T. Moreover, by the assumption U e i = √ 1
n ee i θ , we have M i = ee T . So, ee T ∈ L and, obviously, L r (e) = ee v
TTe (v T L r (e) = e T !), L c (e) = v ee
TTe (L c (e)v = e!).
Thus, ∀ z ∈ C n we have e T L r (z) = z T L r (e) = z vTTe e e T , L c (z)e = L c (e)z = e e
TTz v e.
(2): It is enough to observe that (U H AU ) ii = n 1 e T Ae and use the formula L A = U diag ((U H AU ) jj )U H . However, let us obtain the thesis from (1). As a consequence of (1), the matrix
L
A= U d(U
Tz
rA)d(U
Tv )
−1U
H= U d(U
Hv )
−1d(U
Hz
cA)U
His both e vTTz e
rA-stochastic by columns and e vTTz e
cA-stochastic by rows. Let us prove that e vTTz e
rA = e vTTz e
cA = n 1 e T Ae. Since U H e = √
z e
cA-stochastic by rows. Let us prove that e vTTz e
rA = e vTTz e
cA = n 1 e T Ae. Since U H e = √
z e
cA= n 1 e T Ae. Since U H e = √
ne −iθ e i , we have (z r A ) T e = v T U diag ((U H AU ) jj )U H e = √
ne −iθ v T U e i (U H AU ) ii
= v T e(U H AU ) ii = v T e(U e i ) H A(U e i ) = v T e 1 n e T Ae and, since e T U = √
ne i θ e T i , we have
e T z c A = e T U diag ((U H AU ) jj )U H v = √
ne i θ (U H AU ) ii e T i U H v
= e T v(U H AU ) ii = e T v 1 n e T Ae.
Question: when L c (z) = L r (x) ? Iff U T x = d(u)U H z, u = d(U H v) −1 U T v
[u = e if U ∈ R n ×n (v ∈ R n ) or U = F (v = e 1 ); |u i | = 1 ∀ i].
Third Theorem
Let U, V be two n×n unitary matrices. Choose v, u ∈ C n such that (U T v) i 6= 0, (V T u) i 6= 0, ∀ i. Given z ∈ C n , set
L r (z) = U d(V T z)d(U T v) −1 V H , L c (z) = U d(V H u) −1 d(U H z)V H . Note that v T L r (z) = z T , L c (z)u = z.
Theorem.
If there exists i such that V e i = √ 1 n ee i θ , U e i = √ 1 n ee i ϕ , then V d(U T e)d(U T v) −1 V H =
ee
Te
Tv , U d(V H u) −1 d(V H e)U H = e ee
TTu , and therefore
e T L r (z) = z T V d(U T e)d(U T v) −1 V H = ( z eTTe v )e T , L c (z)e = U d(V H u) −1 d(V H e)U H z = e( e e
TTz u ).
In other words, X ∈ L ⇒ X is s X -stochastic by rows and by columns for some
s X ∈ C. Since, moreover, (U H AV ) ii = n 1 e i (θ−ϕ) e T Ae , if L A = U d(V T z r A )d(U T v) −1 V H = U d(V H u) −1 d(U H z c A )V H = U diag ((U H AV ) jj )V H is the best approximation of
A in L = {Ud(z)V H : z ∈ C n }, then we have that
(z r A ) T e = v T U diag ((U H AV ) jj )V H e = 1 n (e T Ae)v T e, e T (z c A ) = e T U diag ((U H AV ) jj )V H u = n 1 (e T Ae)e T u, and therefore
e T L A = 1
n (e T Ae)e T , L A e = 1
n (e T Ae)e.
It follows that whenever A ∈ C n ×n is stochastic by rows (Ae = e) or stochas- tic by columns (e T A = e T ), its better approximation L A in L is stochastic simultaneously by rows and by columns.
proof. V e i = √ 1
n e i θ e U e i = √ 1
n e i ϕ e ⇒
V
eTe eTv
V
H= e
Te e
Tv
V e
i(V e
i)
H= ee
Te
Tv
h U
eTe eTu
U
H= e
Te e
Tu
U e
i(U e
i)
H= ee
Te
Tu
i .
U e i = √ 1 n e i ϕ e V e i = √ 1 n e i θ e ⇒ e T i U H = √ 1
n e −iϕ e T e T i V H = √ 1
n e −iθ e T ⇒
e
Ti
(U
He ) =
√1n
e
−iϕe
Te =
(UeHTvv)ie
Te , e
Tj
(U
He ) = e
TjU
He
−iϕ√ nU e
i= 0, j 6= i h e
Ti
(V
He ) =
√1n
e
−iθe
Te =
(VeHTuu)ie
Te , e
Tj
(V
He ) = e
TjV
He
−iθ√ nV e
i= 0, j 6= i i
.
Thus we have
d(U H e)d(U H v) −1 =
e
Te e
Tv
d(V H e)d(V H u) −1 =
e
Te e
Tu
,
and therefore V d(U T e)d(U T v) −1 V H = ee eTTv U d(V H u) −1 d(V H e)U H = e ee
TTu .
The equalities V H e = e −iθ √
ne i , e T U = e i ϕ √
ne T i , let us easily obtain the
assertions on L A .
REMARK. L = {Ud(z)V H : z ∈ C n }, U, V unitary, L A = U diag ((U H AV ) jj )V H :
V e i = √ 1
n e i θ e ⇒ L A e = ((U e i ) H Ae)U e i , (U e i ) H L A = (U e
in )
HAe e T ; V e i = √ 1
n e i θ e, U e i = ke e
iϕ≤
k e ≤ , Ae = e ≤ ⇒ L A e = e ≤ , e H ≤ L A = ke
≤n k
2e T ;
U e i = √ 1
n e i ϕ e ⇒ e T L A = (e T AV e i )(V e i ) H , L A (V e i ) = e
TAV e n
ie;
U e i = √ 1 n e i ϕ e, V e i = ke eiθ
≤
k e ≤ , e T A = e H ≤ ⇒ e T L A = e H ≤ , L A e ≤ = ke
≤n k
2e.
Exercise.
Given w ∈ C n , w 6= 0, set M = {X ∈ C n ×n : Xwe T = we T X }. Prove that (i) M is a matrix algebra ;
(ii) M = {X ∈ C n ×n : Xw = cw & e T X = ce T for some c ∈ C}, i.e. X ∈ M implies X is s X -stochastic by columns ;
(iii) if w = e, then M = {X ∈ C n ×n : Xe = ce & e T X = ce T for some c ∈ C}, i.e. X ∈ M implies X is s X -stochastic by rows and by columns.
→ Investigate low complexity spaces L of matrices commuting with we T , in
particular commutative spaces L including we T . We have seen examples in the
case w = e.
Let U be a n × n unitary matrix. Set L = {U(µ ◦ Z)U H : Z ∈ C n×n } where µ is a fixed matrix whose entries are 0 or 1 and ◦ is the entry by entry product.
For example
µ =
1 1 1 1 1
, Z =
z 11 z 12 z 13
z 21 z 22 z 23
z 31 z 32 z 33
, µ ◦ Z =
z 13
z 21 z 22 z 23
z 33
.
Note that if µ = I, then L = {Ud(z)U H : z ∈ C n }.
The space of matrices L is a vector subspace of C n ×n , and is a matrix algebra (i.e. product of matrices from L are in L) if the matrix µ satisfies the condition
[µ] ij = 0 ⇒ [µ 2 ] ij = 0
[or [µ 2 ] ij 6= 0 ⇒ [µ] ij 6= 0; or µ 2 ≤ αµ for some α > 0 (the pattern of µ 2 is enclosed in the pattern of µ)]. Examples of µ satisfying µ 2 ≤ αµ:
µ = I, ee
T,
1 1
,
1 1
,
1 1 1 1
1
,
1 1 1
,
1 1 1 1 1
,
1 1 1 1 1 1
,
1 1 1
1
,
1
1
1 1
,
1
1 1
,
1 1 1
1 1
,
1 1 1 1
,
1 1 1 1 1
.
Given A ∈ C n ×n , and defined L A as the minimizer of kA − U(µ ◦ Z)U H k F , Z ∈ C n×n , we have
L A = U (µ ◦ (U H AU ))U H .
Observe that if µ has a triangular structure, then the eigenvalues of L A are µ jj (U H AU ) jj , j = 1, . . . , n, i.e. null or the same of U diag ((U H AU ) jj )U H .
In the particular case where U e 1 = √ 1 n e i θ e and µ 11 = 1, the matrix µ ◦ (U H AU ) can be written as follows
µ ◦ (U
HAU) =
[
n1e
TAe] · µ
1j[
√1n
e
−iθe
TA(U e
j)] ·
· ·
µ
i1[
√1n
e
iθ(U e
i)
HAe] · µ
ij[(U e
i)
HA(U e
j)] ·
· ·
.
Theorem (stoch by rows).
Assume U e 1 = √ 1 n e i θ e and µ 11 = 1. If Ae = e, then L A e = e and
µ ◦ (U
HAU ) =
1 · µ
1j[
√1ne
−iθe
TA(U e
j)] ·
0 ·
· · µ
ij[(U e
i)
HA(U e
j)] ·
0 ·
.
If moreover µ 1j = 0, j = 2, . . . , n, then
µ ◦ (U
HAU) =
1 0 · 0
0 ·
· · µ
ij[(U e
i)
HA(U e
j)] ·
0 ·
, e
TL
A= e
T.
(thus choose µ ≥ e 1 e T 1 + e 1 e T j for some j in order to have e T L A 6= e T ).
If alternatively A is quasi-stochastic by rows, Ae = e ≤ , with 0 ≤ e ≤ ≤ e, then L A e = eTn e
≤e whenever µ i1 = 0 ∀ i ≥ 2.
proof: investigate the first column in the equality L A U = U (µ ◦ (U H AU )):
L A e = 1
n (e T Ae)e +
n
X
i=1, i6=1
µ i1 ((U e i ) H Ae)U e i .
Theorem (stoch by columns).
Assume U e 1 = √ 1
n e i θ e and µ 11 = 1. If e T A = e T , then e T L A = e T and
µ ◦ (U
HAU) =
1 0 · 0
· ·
µ
i1[
√1n
e
iθ(U e
i)
HAe] · µ
ij[(U e
i)
HA(U e
j)] ·
· ·
.
If moreover µ i1 = 0, i = 2, . . . , n, then
µ ◦ (U
HAU) =
1 0 · 0
0 ·
· · µ
ij[(U e
i)
HA(U e
j)] ·
0 ·
, L
Ae = e.
(thus choose µ ≥ e 1 e T 1 + e i e T 1 for some i in order to have L A e 6= e).
If alternatively A is quasi-stochastic by columns, e T A = e T ≤ , with 0 ≤ e ≤ ≤ e, then e T L A = eTn e
≤e T whenever µ 1j = 0 ∀ j ≥ 2.
proof: investigate the first row in the equality U H L A = (µ ◦ (U H AU ))U H :
e T L A = 1
n (e T Ae)e T +
n
X
j =1, j6=1
µ 1j (e T A(U e j ))(U e j ) H .
Note. If L A and its eigenvalues do not fit our requirements, then we could introduce a perturbation of L A , yet in L, in place of it, for example the matrix
M = L A + U (µ ◦ ( (U H AU ) ◦ ε ))U H , ε ∈ R n×n , |ε ij | small.
Note that
kA − Mk F ≤ kA − L A k F +
s X
i,j, µ
ij=1
|ε ij | 2 |(U H AU ) ij | 2 .
But the Frobenius norm is the right norm?
Results on L A more general than the ones in REMARK, where L = {Ud(z)V H : z ∈ C n }, and the ones in Theorem stoch by columns, and Theorem stoch by rows, where L = {U(µ ◦ Z)U H : Z ∈ C n×n }:
Let U, V be n × n unitary matrices. Set L = {U(µ ◦ Z)V H : Z ∈ C n ×n } where µ is a fixed matrix whose entries are 0 or 1 and ◦ is the entry by entry product.
Note that if µ = I, then L = {Ud(z)V H : z ∈ C n }.
The space of matrices L is a vector subspace of C n×n . In general it is not a matrix algebra.
Given A ∈ C n ×n , and defined L A as the minimizer of kA − U(µ ◦ Z)V H k F , Z ∈ C n ×n , we have
L A = U (µ ◦ (U H AV ))V H .
Observe that if µ has a diagonal structure, then the eigenvalues of L A L H A are µ jj |(U H AV ) jj | 2 , j = 1, . . . , n.
Note that the equalities L A V = U (µ◦(U H AV )) and U H L A = (µ◦(U H AV ))V H imply, respectively,
L A (V e 1 ) = µ 11 (U H AV ) 11 U e 1 + P n
i =1, i6=1 µ i1 (U H AV ) i1 U e i , (U e 1 ) H L A = µ 11 (U H AV ) 11 (V e 1 ) H + P n
j=1, j6=1 µ 1j (U H AV ) 1j (V e j ) H . In the following two theorems e ≤ can be an arbitrary vector with complex entries. However, we think to use the stated results for e ≤ = e (stochastic case) or for e ≤ , 0 ≤ [e ≤ ] j ≤ 1 (quasi-stochastic case).
Theorem (stochastic by rows) V e 1 = √ 1
n e i θ e & µ 11 = 1 ⇒
L
Ae = ((U e
1)
HAe)U e
1+
n
X
i=1, i6=1
µ
i1((U e
i)
HAe)U e
i.
Thus
(i) if Ae = e ≤ & U e 1 = ke eiϕ
≤
k e ≤ , then L A e = e ≤ . If, moreover, µ 1j = 0
∀ j 6= 1, then e H ≤ L A = ke≤n k
2e T .
(ii) if Ae = e ≤ & U e 1 = e √iϕn e , then L A e = e
Tn e
≤e whenever µ i1 = 0 ∀ i 6= 1.
Theorem (stochastic by columns) U e 1 = √ 1 n e i ϕ e & µ 11 = 1 ⇒
e
TL
A= (e
TA(V e
1))(V e
1)
H+
n
X
j=1, j6=1
µ
1j(e
TAV e
j)(V e
j)
H.
Thus
(i) if e T A = e H ≤ & V e 1 = ke eiθ
≤
k e ≤ , then e T L A = e H ≤ . If, moreover, µ i1 = 0
∀ i 6= 1, then L A e ≤ = ke≤n k
2e.
(ii) if e T A = e H ≤ & V e 1 = √ eiθ
n e, then e T L A = e
H
≤
