On the matrix P of the web

On the matrix P of the web

Let n be a positive integer. Let i = 1, 2, . . . , n be the sites of the web. For each site i, let µ i and ν(i) be the number of sites pointed by i and the set whose elements are the sites pointed by i, respectively ( |ν(i)| = µ ⁱ ).

Moreover, for each site i let ρ(i) be the set whose elements are the sites which point to i. Note that the ρ(i) can be computed from the ν(i) via the algorithm:

For i = 1, 2, . . . , n ρ(i) := ∅;

for k = 1, 2, . . . , n

if i ∈ ν(k) then ρ(i) := ρ(i) ∪ {k}

Now let P be the n × n matrix whose ith row, i = 1, . . . , n, has all entries equal to zero except those whose indeces are in ν(i) which are set equal to 1/µ i . Note that

(P x) k =

 1 µ

_k

P

s ∈ν(k) x s ν(k) 6= ∅

0 ν(k) = ∅ , k = 1, 2, . . . , n;

(P ^T x) k =

 P

s ∈ρ(k) 1

µ

s

x s ρ(k) 6= ∅

0 ρ(k) = ∅ , k = 1, 2, . . . , n;

x ^∗ P x =

n

X

k=1

x k (P x) k = X

k:ν(k) 6=∅

x k

1 µ k

X

s ∈ν(k)

x s

= (P ^T x) ^∗ x =

n

X

k=1

(P ^T x) k x k = X

k:ρ(k) 6=∅

x k

X

s ∈ρ(k)

1 µ s

x s .

Example: n = 5,

µ 1 = 0 ν(1) = ∅ µ 2 = 3 ν(2) = {1, 3, 5}

µ 3 = 2 ν(3) = {2, 5}

µ 4 = 0 ν(4) = ∅ µ 5 = 2 ν(5) = {1, 3}

Compute ρ(i), i = 1, 2, 3, 4, 5, and write the 5 × 5 matrix P . On ρ(P ^∗ P ) and v such that P ^∗ P v = ρ(P ^∗ P )v

Upper bounds for ρ(P ^∗ P ):

ρ(P ^∗ P ) = ρ(P P ^∗ ) = kP ^∗ P k ² = kP P ^∗ k ² ≤ kP ^∗ P k ^F = kP P ^∗ k ^F , ρ(P ^∗ P ) ≤ min{min{kP P ^∗ k ¹ , kP ^∗ P k ¹ }, min{kP P ^∗ k ∞ , kP ^∗ P k ∞ }}

(note that kAA ^∗ k ^2,F = kA ^∗ A k ^2,F , ∀A; question: kAA ^∗ k ¹ = kA ^∗ A k ¹ ? ). One can easily prove the identities

(P P ^∗ ) ij = 1

µ i µ j |ν(i) ∩ ν(j)|, (P ^∗ P ) ij = X

k∈ρ(i)∩ρ(j)

1

µ ² _k .

So, we have the bounds

ρ(P ^∗ P ) ≤ |{i : ν(i) 6= ∅}|

min i:ν(i) 6=∅ µ i

and

ρ(P ^∗ P ) ≤ |{i : ρ(i) 6= ∅}| max ⁱ |ρ(i)|

min _k:ν(k)6=∅ µ ² _k . Lower bounds for ρ(P ^∗ P ):

ρ(P ^∗ P ) = kP k ² 2 = max

x,kxk

2

=1 kP xk ² 2 . Thus we have

ρ(P ^∗ P ) ≥ max

i:ρ(i) 6=∅ kP e ⁱ k ² 2 = max

i:ρ(i) 6=∅

X

k ∈ρ(i)

1 µ ² _k ,

ρ(P ^∗ P ) ≥ max

i,j:i 6=j;ρ(i),ρ(j)6=∅ kP 1

√ 2 (e i + e j ) k ² 2

= 1

2 max

i,j:i6=j;ρ(i),ρ(j)6=∅

h X

k∈(ρ(i)∪ρ(j))\(ρ(i)∩ρ(j))

1

µ ² _k + X

k∈ρ(i)∩ρ(j)

4 µ ² _k

i

(check the latter!).

On the other side, from the equality

ρ(P ^∗ P ) = kP k ² 2 = kP ^∗ k ² 2 = max

x,kxk

2

=1 kP ^T x k ² 2

we obtain

ρ(P ^∗ P ) ≥ max

i:ν(i) 6=∅ kP ^T e _i k ² 2 = max

i:ν(i) 6=∅

1 µ i

= 1

min i:ν(i) 6=∅ µ i

,

ρ(P ^∗ P ) ≥ max

i,j:i 6=j;ν(i),ν(j)6=∅ kP ^T 1

√ 2 (e i + e j ) k ² 2

= 1

2 max

i,j:i 6=j;ν(i),ν(j)6=∅

h 1 µ i

+ 1 µ j

+ 2 |ν(i) ∩ ν(j)|

µ i µ j

i (check the latter!).

Check the lower and upper bounds obtained for ρ(P ^∗ P ) when P = ee ^T _i , P = _n ¹ e i e ^T , P = ¹ ₂ e(e i + e j ) ^T , P = _n ¹ (e i + e j )e ^T , e = [1 1 · · · 1] ^T , noting that in all cases the best lower bound can be equal to the upper bound.

Let us associate to P its best circulant approximation:

C P = F diag ((F ^∗ P F ) ii )F ^∗ = √

nF d(F C _P ^T e ₁ )F ^∗ .

It is clear that there are two formulas for the eigenvalues of C P . Let us explicit

these formulas.

(a) Note that (F ^∗ P F ) jj = 1

n X

k:ν(k) 6=∅

X

s ∈ν(k)

1 µ k

ω ^{(s−k)(j−1)} = 1 n

X

k:ρ(k) 6=∅

X

s ∈ρ(k)

1 µ s

ω ^{(k−s)(j−1)}

(use the two expressions obtained above for x ^∗ P x:

(F e j ) ^∗ (P F e j ) = P

k:ν(k) 6=∅ (F e j ) k 1 µ

k

P

s ∈ν(k) (F e j ) s

= P

k:ν(k)6=∅ √ 1

n ω ^{(k −1)(j−1) 1} _µ

k

P

s∈ν(k) √ 1

n ω ^{(s −1)(j−1)} ; (P ^T F e j ) ^∗ (F e j ) = P

k:ρ(k) 6=∅ ( P

s ∈ρ(k) 1

µ

s

(F e j ) s )(F e j ) k

= P

k:ρ(k) 6=∅ ( P

s ∈ρ(k) 1 µ

s

√ 1 n ω ^{(s −1)(j−1)} ) √ ¹ n ω ^{(k −1)(j−1)} . )

(b) Moreover, note that, if s i , i = −n + 1, . . . , −1, 0, 1, . . . , n − 1, denote the sums of the entries on the ith diagonal of P (f.i. . . ., s ₋₁ = P n −1

i=1 (P ) i+1,i , s 0 = P n

i=1 (P ) ii , s 1 = P n−1

i=1 (P ) i,i+1 , . . .), then we have s 0 = 0 and, for i = 1, . . . , n − 1,

s i = X

t=1...n−i,t∈ρ(t+i)

1 µ t

= X

t=1...n−i,t+i∈ν(t)

1 µ t

,

s _−i = X

t=1...n−i,t∈ν(t+i)

1

µ t+i = X

t=1...n−i,t+i∈ρ(t)

1 µ t+i . (In fact, for the s i :

s i = P n −i

t=1 P t,t+i = P n −i

t=1 (P e t+i ) t = P

t=1...n −i, ν(t)6=∅, t+i∈ν(t) 1 µ

t

. The latter equality holds because of the following remark:

(P e t+i ) k =

 1 µ

k

P

s ∈ν(k) (e t+i ) s ν(k) 6= ∅

0 ν(k) = ∅ =

 1

µ

k

ν(k) 6= ∅, t + i ∈ ν(k) 0 otherwise

(P e t+i ) t =

 1

µ

t

ν(t) 6= ∅, t + i ∈ ν(t) 0 otherwise

Analogously,

s i = P n −i

t=1 P t,t+i = P n −i

t=1 (P ^T e _t ) t+i

= P

t=1...n −i, ρ(t+i)6=∅

P

s ∈ρ(t+i) 1 µ

s

(e t ) s

= P

t=1...n −i, ρ(t+i)6=∅, t∈ρ(t+i) 1 µ

t

. Example: s 1 = P

t=1...n −1, t:t→t+1 1 µ

t

. . ..

For the s _−i :

s _−i = P n−i

t=1 P t+i,t = P n−i

t=1 (P e t ) t+i

= P

t=1...n−i, ν(t+i)6=∅ 1 µ

t+i

P

s∈ν(t+i) (e t ) s , s _−i = P n −i

t=1 P t+i,t = P n −i

t=1 (P ^T e _t+i ) t

= P

t=1...n −i, ρ(t)6=∅

P

s ∈ρ(t) 1

µ

s

(e t+i ) s .

)

It can be shown that the first row of C P , say c ^T = [c 0 c 1 · · · c ⁿ −1 ], can be computed via the identities

c 0 = s 0 /n = 0, c i = (s i + s _−n+i )/n, i = 1, . . . , n − 1.

So, C P = F d(z)F ^∗ , z = √ nF c.

Any time something in the web changes, we have to update P and C P . In particular, we have to compute the new s i in order to define the new c i and thus the new vector z (of the eigenvalues of C P ). Now we show how such new s i can be computed from the old s i , in the main situations that may occur.

Case 1: nascita di un sito

P old → P new =

 P old 0

· · · µ

n+1

¹ · · · 0



We call the new site n + 1, and we associate to it the new objects µ n+1 =?, ν(n + 1) = {?} ⊂ {1, 2, . . . , n}, ρ(n + 1) = ∅ (we need new memory allocations for them). We assume µ n+1 = |ν(n + 1)| small (µ ⁿ⁺¹ ≥ 1 (?)).

Then we introduce two new numbers s n , s _−n (we need other two new cells in memory for them), and we set:

s n := 0, s _−n := 0, s j −n−1 := s j −n−1 + 1 µ n+1

, j ∈ ν(n + 1).

After this, we introduce another new number c n (we need a further new cell in memory for it), and we set:

c n := 0, c j := (s j + s _−(n+1)+j )/n, j ∈ ν(n + 1).

Finally, set n := n + 1.

Case 2: morte di un sito contemporanea alla nascita di un altro

P old =



 · µ ¹

r

· 0 · µ ¹

r

·



 → P new =





0

· µ

^new_r

¹ · 0 · µ

^new_r

¹ · 0





Assume that the site r dies. Then we have to set s k −r := s k −r − 1

µ r

, k ∈ ν(r),

and apply (4) (see below) for j = r and ∀i ∈ ρ(r). Assume now that at the same time a new site is created. We call it r and we associate to it µ r =?, ν(r) = {?} ⊂ {1, 2, . . . , n}\{r}, ρ(r) = ∅ (i.e. we use the memory allocations of the died site). We assume µ r = |ν(r)| small (µ ^r ≥ 1 (?)). Then we have to set

s k −r := s k −r + 1 µ r

, k ∈ ν(r).

After this, we set

c _k−r = (s _k−r + s _−n+k−r )/n, k ∈ ν(r), k − r > 0,

c n+k −r = (s n+k −r + s k −r )/n, k ∈ ν(r), k − r < 0.

3: Site i decides to point to the site j

P old =



 · µ ¹

i

· 0 · · ·



 → P new =



 · µ

i

¹ +1 · µ

i

¹ +1 · · ·



 First we have to set:

s j −i := s j −i + 1

µ i + 1 , s k −i := s k −i + 1 µ i + 1 − 1

µ i , k ∈ ν(i).

Then set

c j −i = (s j −i + s _−n+j−i )/n, if j − i > 0, or c n+j −i = (s n+j −i + s j −i )/n, if j − i < 0, and c k −i = (s k −i + s _−n+k−i )/n, k ∈ ν(i), k − i > 0,

c n+k −i = (s n+k −i + s k −i )/n, k ∈ ν(i), k − i < 0.

Finally, we set µ i := µ i + 1, ν(i) := ν(i) ∪ {j}, ρ(j) := ρ(j) ∪ {i}. The latter identities require reordering (forward shift).

4: Site i decides not to point to the site j anymore

P old =



 · µ ¹

i

· µ ¹

i

· · ·



 → P new =



 · µ

i

¹ −1 · 0 · · ·



 First we have to set:

s j −i := s j −i − 1 µ i

, s k −i := s k −i + 1 µ i − 1 − 1

µ i

, k ∈ ν(i)\{j}.

Then set

c j −i = (s j −i + s _−n+j−i )/n, if j − i > 0, or c n+j −i = (s n+j −i + s j −i )/n, if j − i < 0, and c _k−i = (s _k−i + s _−n+k−i )/n, k ∈ ν(i)\{j}, k − i > 0,

c _n+k−i = (s _n+k−i + s _k−i )/n, k ∈ ν(i)\{j}, k − i < 0.

Finally, we set µ i := µ i − 1, ν(i) := ν(i)\{j}, ρ(j) := ρ(j)\{i}. The latter identities require reordering (backward shift).

Remark Note that, after case 1 or case 2 has been run, the site i ^∗ which has created the new site (n in Case 1 and r in case 2) must have a link to such new site. In other words, after case 1 or case 2 we have to run (3) for j = n and i = i ^∗ ∈ {1, . . . , n − 1} or for j = r and i = i ^∗ ∈ {1, . . . , n}\{r}.

An algorithm generating the test matrix P and the corresponding approxi- mation C P

Given a natural number N one could generate a test matrix P of order N and,

simultaneously, its best circulant approximation C P (or, more precisely: non

negative integers µ 1 , . . . , µ N and sets ν(1), . . . , ν(N ) defining P ; and real num-

bers s _−N+1 , . . . , s 0 , . . . , s _N−1 , c 0 , . . . , c _N−1 , z 1 , . . . , z N defining C P = F d(z)F ^∗ )

by the following procedure:

• Consider an initial matrix matrix P of small size (i.e. choose a small n and define µ i ,ν(i), i = 1, . . . , n)

• Apply to P the operators (Case 1)-(3),(Case 2)-(3),(3),(4) repeatedly, in suitable order, each possibly more times, until n is equal to N . During this phase, for what concerns C P , update only the s i . (Note that the operator (Case 2)-(3) requires |ρ(r)| applications of (4); so it is expensive if |ρ(r)|

is large. However, the death of r means generally a small |ρ(r)| )

• When n = N compute also the first row c ^T of C P and the vector z = √ nF c of the eigenvalues of C P

Note that it is advisable to choose N as a power of 2, so that the F F T involved (in computing the vector z defining the preconditioner C P , and in each step of the Richardson method preconditioned by C P ) are more efficient.

Upper and lower bounds for ρ(P ^∗ P ) A first upper bound is obtained as follows:

pρ(P ^∗ P ) = kP k ² = kP ^∗ k ² = max _x:kxk

₂

=1 kP ^T x k ²

≤ max x:kxk

2

=1 kP ^T x k ¹

= max _x:kxk

₂

=1 P

i |( P

s:ν(s) 6=∅ x s P ^T e _s ) i |

= max _x:kxk

₂

=1 P

i | P

s:ν(s) 6=∅ x s (P ^T ) i,s |

≤ max x:kxk

²

=1 P

i

P

s:ν(s)6=∅ |x ^s |(P ^T ) i,s

= max _x:kxk

₂

=1 P

s:ν(s) 6=∅ |x ^s | P

i (P ^T ) i,s

= max _x:kxk

₂

=1 P

s:ν(s) 6=∅ |x ^s |

= max _x:kxk

2

=1&x

k

=0, ∀k ν(k)=∅ P

s:ν(s)6=∅ |x ^s |

= p|{s : ν(s) 6= ∅}|.

However, a lower upper bound can be obtained. In fact, we have that ρ(P ^∗ P ) ≤ d where

d = min { |{i : ν(i) 6= ∅}|

min _i:ν(i)6=∅ µ i

, |{i : ρ(i) 6= ∅}| max ⁱ |ρ(i)|

min _k:ν(k)6=∅ µ ² _k }.

Proof.

kP P ^∗ k ∞ = max i P

j |(P P ^∗ ) ij | = max ⁱ P

j 1

µ

i

µ

j

|ν(i) ∩ ν(j)|

= max i 1 µ

i

P

j 1

µ

j

|ν(i) ∩ ν(j)|

= max i 1 µ

i

P

j:ν(j) 6=∅ 1

µ

j

|ν(i) ∩ ν(j)|

≤ max ⁱ µ ¹

i

P

j:ν(j) 6=∅

1

µ

j

µ j = max i 1

µ

i

|{j : ν(j) 6= ∅}|

= |{j : ν(j) 6= ∅}| min

i:ν(i)6=∅

¹ µ

i

, kP ^∗ P k ∞ = max i P

j |(P ^∗ P ) ij | = max ⁱ P

j

P

k ∈ρ(i)∩ρ(j) 1 µ

²_k

≤ max ⁱ min

k:ν(k)6=∅

¹ µ

²_k

P

j

P

k ∈ρ(i)∩ρ(j) 1

= max i 1

min

_k:ν(k)6=∅

µ

²_k

P

j |ρ(i) ∩ ρ(j)|

= max i 1

min

_k:ν(k)6=∅

µ

²_k

P

j:ρ(j) 6=∅ |ρ(i) ∩ ρ(j)|

≤ |{j : ρ(j) 6= ∅}| max ^k |ρ(k)| min

_k:ν(k)6=∅

¹ µ

²_k

.  (Question: is the following inequality

|{j : ν(j) 6= ∅}|

min i:ν(i) 6=∅ µ i ≤ |{j : ρ(j) 6= ∅}| max ^k |ρ(k)|

min k:ν(k) 6=∅ µ ² _k

or, equivalently,

|{j : ρ(j) 6= ∅}| max _k |ρ(k)| ≥ |{j : ν(j) 6= ∅}| min

k:ν(k) 6=∅ |ν(k)|

true? Note that

max k |ρ(k)| ≤ |{j : ν(j) 6= ∅}|,

|{j : ρ(j) 6= ∅}| ≥ max ^k |ν(k)| ≥ min k:ν(k)6=∅ |ν(k)|.

)

Let us now obtain lower bounds for ρ(P ^∗ P ) more general than those obtained in the previous section.

Choose x = √ ¹

3 (e i + e j + e k ), i, j, k distinct, in ρ(P ^∗ P ) ≥ kP ^T x k ² 2 , kxk ² = 1, in order to obtain

ρ(P ^∗ P ) ≥ r ³ = ¹ ₃ max i,j,k:i,j,k distinct, ν(i),ν(j),ν(k) 6=∅

h 1

µ

i

+ _µ ¹

_j

+ _µ ¹

k

+ 2|ν(i)∩ν(j)|

µ

i

µ

j

+ 2|ν(i)∩ν(k)|

µ

i

µ

k

+ 2|ν(j)∩ν(k)|

µ

j

µ

k

i . Note that if

P = 1

n (e i + e j + e k )e ^T ,

then in the above inequality the equal sign holds, i.e. d = ρ(P ^∗ P ) = r 3 = 3/n.

Choose x = ^{√ 1}

3 (e i + e j + e k ), i, j, k distinct, in ρ(P ^∗ P ) ≥ kP xk ² 2 , kxk ² = 1, in order to obtain

ρ(P ^∗ P ) ≥ c ³ = ¹ ₃ max _A

3

⊂{i:ρ(i)6=∅}, |A

³

|=3

h P

i ∈A

3

P

s ∈ρ(i)\∪

j∈A3 \{i}

ρ(j) 1 µ

²_s

+ P

i ∈A

3

P

s ∈(∩

j∈A3\{i}

ρ(j)) \ρ(i) 4 µ

²_s

+ P

s ∈∩

i∈A3

ρ(i) 9 µ

²_s

i .

Note that if

P = 1

3 e(e i + e j + e k ) ^T ,

then in the above inequality the equal sign holds, i.e. d = ρ(P ^∗ P ) = c 3 = n/3.

We guess that the following results (r) and (c) hold:

(r) Set r k = 1

k max

A

k

⊂{i:ν(i)6=∅},|A

k

|=k

h X

r ∈A

k

1 µ r

+ X

r,s ∈A

k

,r<s

2

µ r µ s |ν(r) ∩ ν(s)| i .

Then

r k ≤ ρ(P ^∗ P ) ≤ d, ∀k ∈ {1, . . . , |{i : ν(i) 6= ∅}|}.

(Proof: apply the inequality

ρ(P ^∗ P ) = kP ^∗ k ² 2 ≥ kP ^T x k ² 2 , kxk ² = 1, for x = ^{√ 1} _k (e i

1

+ . . . + e i

_k

), 1 ≤ i ¹ < i 2 < . . . < i k ≤ n).

Note that if P = 1

n (e i

1

+ e i

2

+ . . . + e i

k

)e ^T , 1 ≤ i ¹ < i 2 < . . . < i k ≤ n, then r k = ρ(P ^∗ P ) = d = _n ^k .

(c) Now set

c k = 1

k max

A

k

⊂{i:ρ(i)6=∅},|A

k

|=k

h X ^k

r=1

X

γ

r

⊂A

k

, |γ

r

|=r

X

s ∈∩

j∈γr

ρ(j) \∪

j∈Ak \γr

ρ(j)

r ² µ ² _s

i .

Then

c k ≤ ρ(P ^∗ P ) ≤ d, ∀k ∈ {1, . . . , |{i : ρ(i) 6= ∅}|}.

(Proof: apply the inequality

ρ(P ^∗ P ) = kP k ² 2 ≥ kP xk ² 2 , kxk ² = 1, for x = ^{√ 1} _k (e i

1

+ . . . + e i

k

), 1 ≤ i ¹ < i 2 < . . . < i k ≤ n).

Note that if P = 1

k e(e i

1

+ e i

2

+ . . . + e i

k

) ^T , 1 ≤ i ¹ < i 2 < . . . < i k ≤ n, then c k = ρ(P ^∗ P ) = d = ⁿ _k .

Remark. By choosing k = 1, k = 2 and k = 3 in the above statements we retrieve the lower bounds for ρ(P ^∗ P ) obtained explicitly.

If the lower bounds in (r) and (c) for ρ(P ^∗ P ) are true, then we can say that max { max

1,..., |{i:ν(i)6=∅}| r k , max

1,..., |{i:ρ(i)6=∅}| c k } ≤ ρ(P ^∗ P ) ≤ d d = min { |{i : ν(i) 6= ∅}|

min _i:ν(i)6=∅ µ i

, |{i : ρ(i) 6= ∅}| max ⁱ |ρ(i)|

min _k:ν(k)6=∅ µ ² _k }.

Question: is the sequence max {r ^k , c k }, k = 1, . . ., non decreasing? If yes, then one could compute its terms to obtain better and better lower bounds for ρ(P ^∗ P ).

Examples.

c) P = ee ^T _i , d = n r 1 = 1, c 1 = n r 2 = 2, c 2 =und r 3 = 3, c 3 =und

cc) P = ¹ ₂ e(e i + e j ) ^T , d = n/2 r 1 = 1/2, c 1 = n/4

r 2 = 1, c 2 = n/2

r 3 = 3/2, c 3 =und r) P = ¹ _n e i e ^T , d = 1/n r 1 = 1/n, c 1 = 1/n ² r 2 =und, c 2 = 2/n ² r 3 =und, c 3 = 3/n ²

rr) P = ¹ _n (e i + e j )e ^T , d = 2/n r 1 = 1/n, c 1 = 2/n ²

r 2 = 2/n, c 2 = 4/n ² r 3 =und, c 3 = 6/n ² Set ˜ e = P t

i=1 e _i . c1) P = ˜ ee ^T _i , d = t r 1 = 1, c 1 = t r 2 = 2, c 2 =und r 3 = 3, c 3 =und

cc1) P = ¹ ₂ ˜ ee ^T _i + (e − ¹ 2 ˜ e)e ^T _j , d = n r 1 = 1, c 1 = t/4 + (n − t)

r 2 = 2, c 2 = n/2 r 3 = 3, c 3 =und r1) P = ¹ _t e _i ˜ e ^T , d = 1/t r 1 = 1/t, c 1 = 1/t ² r 2 =und, c 2 = 2/t ² r 3 =und, c 3 = 3/t ²

rr1) P = _n ¹ e _i e ^T + ¹ _t e _j ˜ e ^T , d = 2/t r 1 = 1/t, c 1 = 1/t ² + 1/n ²

r 2 = ¹ ₂ (3/n + 1/t), c 2 = 2/t ² + 2/n ² r 3 =und, c 3 = 3/t ² + 3/n ² (?) Question: from the equality

ρ(P ^∗ P ) = ρ(P P ^∗ ) = inf

k ( k(P P ^∗ ) ^k k ∞ ) ^1/k = lim

k ( k(P P ^∗ ) ^k k ∞ ) ^1/k

is it possible to define a non increasing sequence d k such that d 0 = d = |{i : ν(i) 6= ∅}|/ min µ ^k (recall that kP P ^∗ k ∞ ≤ d) and ρ(P P ^∗ ) ≤ d ^k ≤ d, ∀ k ? If yes, then one could compute its terms to obtain better and better upper bounds for ρ(P ^∗ P ).

The proof of an inequality We now prove the inequality:

( min

k:ν(k) 6=∅ |ν(k)|) |{j : ν(j) 6= ∅}| ≤ (max _k |ρ(k)|) |j : ρ(j) 6= ∅|.

So, for the d in the upper bound ρ(P ^∗ P ) ≤ d (see above) we simply have d = |{k : ν(k) 6= ∅}|

min k:ν(k) 6=∅ µ k

. Without loss of generality, assume that

{j : ν(j) 6= ∅} = {1, 2, . . . , x}, x := |{j : ν(j) 6= ∅}|,

{j : ρ(j) 6= ∅} = {1, 2, . . . , y}, y := |{j : ρ(j) 6= ∅}|.

Thus, the x ×y upper left submatrix of P , which we call W , has no null row and no null column, whereas the entries of the remaining part of P are all zeroes:

P =

 W 0

0 0

 . (1) If min k:ν(k) 6=∅ |ν(k)| = 1, then x ≤ (max ^k |ρ(k)|)y.

Proof. We prove the thesis considering the two different cases y ≥ x and y < x. It is useful to observe that, by the hypotheses, the nonzero entries of the matrix W for y = x, ^x ₂ , ^x ₃ , . . . , ^x _i , _i+1 ^x must be (modulo permutations) in the positions shown in Figure 1.

y ≥ x: In this case max ^k |ρ(k)| ≥ 1 (see Figure 1, y = x). Thus 1 · x ≤ 1 · y ≤ (max k |ρ(k)|)y.

y < x: If y < x, then max k |ρ(k)| ≥ 2 (see Figure 1, y = x, ^x 2 ). If ^x ₂ ≤ y too, then x ≤ 2y ≤ (max ^k |ρ(k)|)y. If y < ^x 2 , then max k |ρ(k)| ≥ 3 (see Figure 1, y = ^x ₂ , ^x ₃ ). If ^x ₃ ≤ y too, then x ≤ 3y ≤ (max ^k |ρ(k)|)y. In general, let i ∈ {1, 2, . . .}. If y < ^x i , then max k |ρ(k)| ≥ i + 1 (see Figure 1, y = ^x i , _i+1 ^x ). If

x

i+1 ≤ y too, then x ≤ (i + 1)y ≤ (max ^k |ρ(k)|)y.

Figure 1: W for min µ k = 1, y = x, ^x ₂ , ^x ₃ , . . . , ^x _i , _i+1 ^x







 ,















 ,

























· · ·































 ,







































 (2) If min k:ν(k) 6=∅ |ν(k)| = 2, then 2x ≤ (max ^k |ρ(k)|)y.

Proof. We prove the thesis considering the two different cases y ≥ 2x and y < 2x. It is useful to observe that, by the hypotheses, the nonzero entries of the matrix W for y = 2x, 2 ^x ₂ , 2 ^x ₃ , . . . , 2 ^x _i , 2 _i+1 ^x must be (modulo permutations) in the positions shown in Figure 2.

y ≥ 2x: In this case max ^k |ρ(k)| ≥ 1 (see Figure 2, y = 2x). Thus 2x ≤ 1 · y ≤ (max ^k |ρ(k)|)y.

y < 2x: If y < 2x, then max k |ρ(k)| ≥ 2 (see Figure 2, y = 2x, 2 ^x 2 ). If 2 ^x ₂ ≤ y too, then 2x ≤ 2y ≤ (max ^k |ρ(k)|)y. If y < 2 ^x 2 , then max k |ρ(k)| ≥ 3 (see Figure 2, y = 2 ^x ₂ , 2 ^x ₃ ). If 2 ^x ₃ ≤ y too, then 2x ≤ 3y ≤ (max ^k |ρ(k)|)y. In general, let i ∈ {1, 2, . . .}. If y < 2 ^x i , then max k |ρ(k)| ≥ i + 1 (see Figure 2, y = 2 ^x i , 2 _i+1 ^x ).

If 2 _i+1 ^x ≤ y too, then 2x ≤ (i + 1)y ≤ (max ^k |ρ(k)|)y.

Figure 2: W for min µ k = 2, y = 2x, 2 ^x ₂ , 2 ^x ₃ , . . . , 2 ^x _i , 2 _i+1 ^x









,

















,

























· · ·

































,









































(3) If min k:ν(k) 6=∅ |ν(k)| = 3, then 3x ≤ (max ^k |ρ(k)|)y.

Proof. We prove the thesis considering the two different cases y ≥ 3x and y < 3x. It is useful to observe that, by the hypotheses, the nonzero entries of the matrix W for y = 3x, 3 ^x ₂ , 3 ^x ₃ , . . . , 3 ^x _i , 3 _i+1 ^x must be (modulo permutations) in the positions shown in Figure 3.

y ≥ 3x: In this case max ^k |ρ(k)| ≥ 1 (see Figure 3, y = 3x). Thus 3x ≤ 1 · y ≤ (max ^k |ρ(k)|)y.

y < 3x: If y < 3x, then max k |ρ(k)| ≥ 2 (see Figure 3, y = 3x, 3 ^x 2 ). If 3 ^x ₂ ≤ y too, then 3x ≤ 2y ≤ (max ^k |ρ(k)|)y. If y < 3 ^x 2 , then max k |ρ(k)| ≥ 3 (see Figure 3, y = 3 ^x ₂ , 3 ^x ₃ ). If 3 ^x ₃ ≤ y too, then 3x ≤ 3y ≤ (max ^k |ρ(k)|)y. In general, let i ∈ {1, 2, . . .}. If y < 3 ^x i , then max k |ρ(k)| ≥ i + 1 (see Figure 3, y = 3 ^x i , 3 _i+1 ^x ).

If 3 _i+1 ^x ≤ y too, then 3x ≤ (i + 1)y ≤ (max ^k |ρ(k)|)y.

Figure 3: W for min µ k = 3, y = 3x, 3 ^x ₂ , 3 ^x ₃ . . . , 3 ^x _i , 3 _i+1 ^x









,

















,

























· · ·

































,









































(4) (min k:ν(k) 6=∅ |ν(k)|)x ≤ (max ^k |ρ(k)|)y.

Proof. Set µ min = min k:µ

_k

>0 µ k . We prove the thesis considering the two different cases y ≥ µ ^min x and y < µ min x. It is useful to observe that, by the hypotheses, the nonzero entries of the matrix W for y = µ min x, µ min x

2 , µ min x 3 , . . ., µ min x

i , µ min x

i+1 must be (modulo permutations) in the positions shown in Figure 4.

y ≥ µ ^min x: In this case max k |ρ(k)| ≥ 1 (see Figure 4, y = µ ^min x). Thus µ min x ≤ 1 · y ≤ (max ^k |ρ(k)|)y.

y < µ min x: If y < µ min x, then max k |ρ(k)| ≥ 2 (see Fig.4, y = µ ^min x, µ min x 2 ).

If µ min x

2 ≤ y too, then µ ^min x ≤ 2y ≤ (max ^k |ρ(k)|)y. If y < µ ^{min x} 2 , then max k |ρ(k)| ≥ 3 (see Figure 4, y = µ ^{min x} 2 , µ min x

3 ). If µ min x

3 ≤ y too, then µ min x ≤ 3y ≤ (max ^k |ρ(k)|)y. In general, let i ∈ {1, 2, . . .}. If y < µ ^{min x} i , then max k |ρ(k)| ≥ i + 1 (see Figure 4, y = µ ^{min x} i , µ min x

i+1 ). If µ min x

i+1 ≤ y too, then µ min x ≤ (i + 1)y ≤ (max ^k |ρ(k)|)y.

Figure 4: W for µ min generic, y = µ min x, µ min x 2 , µ min x

3 . . . , µ min x

i , µ min x i+1









,

















,

























· · ·

































,









































Better upper bounds for ρ(P ^∗ P ) ?

Let i, j ∈ {1, 2, . . . , n}. If ν(i) = ∅ or ν(j) = ∅, then ((P P ^∗ ) ^k ) ij = 0, for all k ≥ 1. Otherwise, i.e. if both ν(i) and ν(j) are non empty, then

(P P ^∗ ) ij = 1

µ i µ j |ν(i) ∩ ν(j)|, ((P P ^∗ ) ² ) ij = 1

µ i µ j

X

k:ν(k)6=∅

|ν(i) ∩ ν(k)| |ν(k) ∩ ν(j)|

µ ² _k ,

((P P ^∗ ) ³ ) ij = 1 µ i µ j

X

k,s:ν(k),ν(s) 6=∅

|ν(i) ∩ ν(k)| |ν(k) ∩ ν(s)| |ν(s) ∩ ν(j)|

µ ² _k µ ² _s ,

. . .

((P P

^∗

)

^k

)

ij

= 1 µ

i

µ

j

X

r₁,...,r_k−1:ν(rs)6=∅, ∀ s

|ν(i) ∩ ν(r

1

)||ν(r

1

) ∩ ν(r

2

)|· · ·|ν(r

k−1

) ∩ ν(j)|

µ

²r₁

µ

²r₂

· · ·µ

²r_k−1

,

((P P ^∗ ) ^k+1 ) ij = 1 µ j

X

r

k

:ν(r

k

) 6=∅

|ν(r ^k ) ∩ ν(j)|

µ r

k

((P P ^∗ ) ^k ) i,r

k

.

Aim: find a sequence d k such that ρ(P ^∗ P ) ≤ d ^k+1 ≤ d ^k ≤ d ⁰ , d k → ρ(P ^∗ P ).

Recall that

ρ(P ^∗ P ) = ρ(P P ^∗ ) = ((ρ(P P ^∗ )) ^k )

^1k

= (ρ((P P ^∗ ) ^k ))

^1k

≤ k(P P ^∗ ) ^k k

^k1

≤ kP P ^∗ k, k = 1, 2, . . . , ρ(P P ^∗ ) = inf

k k(P P ^∗ ) ^k k

^1k

= lim

k k(P P ^∗ ) ^k k

^k1

, kP P ^∗ k ∞ = max

i:µ

i

>0

X

j:µ

_j

>0

|ν(i) ∩ ν(j)|

µ i µ j ≤ d ⁰ := d = |{j : ν(j) 6= ∅}|

µ min

.

Thus, from the inequality

k(P P ^∗ ) ² k ∞ = max i:µ

i

>0 1 µ

i

P

j:µ

j

>0 1 µ

j

P

k:µ

k

>0 |ν(i)∩ν(k)||ν(k)∩ν(j)|

µ

²_k

≤ max ^i:µ

i

>0 1 µ

²_i

P

j:µ

j

>0 |ν(i)∩ν(j)|

µ

j

2

= kP P ^∗ k ² _∞ ≤ d ² 0 , we have that a first step towards our aim, could be the following: look for d 1

such that

k(P P ^∗ ) ² k ∞ = max

i:µ

i

>0

1 µ i

X

j:µ

j

>0

1 µ j

X

k:µ

k

>0

|ν(i) ∩ ν(k)| |ν(k) ∩ ν(j)|

µ ² _k ≤ d ² 1 , d 1 < d 0 . (Note that

ρ(P P ^∗ ) ≤ . . . ≤ k(P P ^∗ ) ⁸ k ∞

¹⁸

≤ k(P P ^∗ ) ⁴ k ∞

¹⁴

≤ k(P P ^∗ ) ² k ∞

¹²

≤ k(P P ^∗ ) k ∞ , k(P P ^∗ ) ²

^k

k

1

∞

2k

→ ρ(P P ^∗ ).

So, the ideal result we would like to obtain is the following: define an easily computable number d k such that

k(P P ^∗ ) ²

^k

k

1

∞

2k

≤ d ^k ≤ k(P P ^∗ ) ²

^k−1

k

1

∞

2k−1

, k = 1, 2, . . . . )

Computing ν(i) ∩ ν(j), |ν(i) ∩ ν(j)| and (P P ^∗ ) ij = |ν(i)∩ν(j)|

µ

i

µ

j

The following algorithm for i = 1, . . . , n {

m i := null; (m i (j) := ( ∅, 0, 0) ∀ j = 1, . . . , n) if ν(i) 6= ∅ (µ ⁱ > 0) then {

η i := ν(i); c i := µ i ; f i := 1/µ i ; for j = i + 1, . . . , n {

η j = ∅; c ^j = 0;

for k ∈ ν(i) { if k ∈ ν(j) then {

η j := η j ∪ {k};

c j := c j + 1 } } (η ^j = ν(i) ∩ ν(j), c ^j = |ν(i) ∩ ν(j)|) if c j > 0 then { f ^j := c j /(µ i µ j )

}

for j = i, . . . , n { (η ^j 6= ∅ for at least j = i) m i (j) := (η j , c j , f j ) }

for j = 1, . . . , i − 1 { m ⁱ (j) := m j (i) } (m ⁱ 6= null) }

}

yields the vectors m i here below:

m 1 = [( , ) . . .]

. . .

m i = [( , ) . . . (ν(i) ∩ ν(j), |ν(i) ∩ ν(j)|, |ν(i)∩ν(j)|

µ

i

µ

j

) . . . ( , )]

. . .

m n = [( , ) . . .].

Question: is it possible to compute k(P P ^∗ ) ²

^k

k ∞ from k(P P ^∗ ) ²

^k−1

k ∞ with less than |{j : ν(j) 6= ∅}| ³ arithmetic operations ?

ρ(H) as the limit of a sequence (written about two years ago) (Given γ k ∈ S ⊂ X and γ ∈ X, by writing

γ k → γ

we mean the convergence to zero of the sequence of non negative real numbers ξ k = kγ ^k − γk, where k may be the absolute value (X = R, C), a vector norm (X = R ⁿ , C ⁿ ), a matrix norm (X = R ^{n ×n} , C ^{n ×n} ), a functional norm (X = C ⁰ , L ² ).)

Let H be a n × n matrix and ρ ^k the sequence of non negative real numbers ρ k = ( kH ^k k) ^1/k , k ≥ 1.

It is simple to verify that ρ(H) ≤ ρ ^k ≤ ρ ¹ = kHk, ∀k and that . . . ρ ⁸ ≤ ρ ⁴ ≤ ρ 2 ≤ ρ ¹ ; . . . ρ 6 ≤ ρ ³ ≤ ρ ¹ ; . . .. It is not simple to establish if the sequence ρ k is non increasing or not. In particular, is it true that

ρ 3 ≤ ρ ² ? (surely we have ρ 3 ≤ ρ ² kHk ^1/3 kH ² k ^1/6 )

However, even if we succeed in proving the non increasing behaviour of ρ k , or, more simply, the convergence of ρ k , we could only conclude that

ρ(H) ≤ lim _k ρ n ≤ ρ ^s .

In the following theorem, instead, it is noticed that a stronger result holds: the sequence ρ k converges (from above) to ρ(H).

Lemma Given H ∈ C ^{n ×n} and ε > 0 there exists a matrix norm ˆ k = ˆk ^H,ε such that ˆ kHˆk < ρ(H) + ε.

Proof. The thesis is verified, for example, by setting ˆ kAˆk = kSAS ⁻¹ k ∞

where S = DQ, with Q unitary such that T = QAQ ⁻¹ is upper triangular, and D diagonal with D ii = 1/δ ⁱ , δ suitable.

Theorem Given H ∈ C ^{n ×n} , indipendently from the choice of the matrix norm k · k, we have

ρ(H) = lim

k kH ^k k

k¹

.

Proof. Set ρ = inf ρ k , for a particular choice of k. Then it can be shown that ρ k , for any choice of k, converges to ρ. It follows that the definition of ρ does not depend upon the choice of k. Since ρ ^k ≥ ρ(H), we have ρ ≥ ρ(H). But we also have ε + ρ(H) > ρ, for any ε > 0. In fact, by the Lemma there exists ˆ k such that (ˆ kH ^k ˆ k) ^1/k ≤ ˆkHˆk < ρ(H) + ε, and ρ = inf(ˆkH ^k ˆ k) ^1/k . Thus ρ must be equal to ρ(H). QED

Problem: ρ 1 ≥ ρ ² ≥ ρ ⁴ ≥ ρ ⁸ ≥ . . ., are better and better approximations of ρ(H). Is it possible to introduce a norm k · k such that these approximations are easily computable and converge rapidly to ρ(H) ?

Corollary Given H ∈ C ^{n ×n} , H ^k → 0 if and only if ρ(H) < 1.

Proof. ρ(H) < 1 ⇒ (kH ^k k) ^1/k ≤ ν < 1, ∀k ≥ N ⇒ kH ^k k ≤ ν ^k ⇒ kH ^k k → 0. Viceversa, kH ^k k → 0 ⇒ ∃k : kH ^k k < 1 ⇒ ∃k : ρ(H) ^k = ρ(H ^k ) < 1

⇒ ρ(H) < 1. QED