T 0 (x) = 1, T 1 (x) = x, T k (x) = 2T k −1 (x)x − T k −2 (x), k = 2, 3, . . . , and recall their alternative representation in [−1, 1]

(1)

A new matrix algebra ?

Let T j (x) be the Chebycev polynomials

T 0 (x) = 1, T 1 (x) = x, T k (x) = 2T k −1 (x)x − T ^k −2 (x), k = 2, 3, . . . , and recall their alternative representation in [−1, 1]

T k (x) = cos(k arccos x), x ∈ [−1, 1].

Some of them: T 2 (x) = 2x ² − 1, T ³ (x) = 4x ³ − 3x, T ⁴ (x) = 8x ⁴ − 8x ² + 1, . . . Let X be a n × n matrix with the property that the set L of all polynomials in X has dimension n (i.e. maximum dimension, since by Cayley-Hamilton theorem if p X (λ) is the characteristic polynomial of X then p X (X) = 0). Usually an X with such property is called non-derogatory. Consider the Chebycev basis of L:

J 1 = T 0 (X) = I, J 2 = T 1 (X) = X,

J k+1 = T k (X) = 2T k −1 (X)X − T k −2 (X), k = 2, 3, . . . , n − 1.

We are interested in cases where A = P

k a k J k means v ^T A = [a 1 a 2 · · · a ⁿ ] for some vector v.

For instance, choose

X =





0 1 0 a b c 0 d e



 . Then

J 1 = I, J 2 = X =





0 1 0 a b c 0 d e



 ,

J 3 = T 2 (X) = 2T 1 (X)X − T ⁰ (X) = 2X ² − I

= 2





a b c

ba a + b ² + cd bc + ce da db + ed dc + e ²



 − I.

Note that the first row of J 3 is [2a − 1 2b 2c] and thus is equal to [0 0 1] iff a = ¹ ₂ , b = 0, c = ¹ ₂ . So, for these particular choices of a, b, c we have e ^T ₁ J k = e ^T _k , k = 1, 2, 3, i.e. A = P 3

k=1 a k J k means e ^T ₁ A = [a 1 a 2 a 3 ]. Moreover, since a = ¹ ₂ , b = 0, c = ¹ ₂ imply

J 3 =





0 0 1

0 d e

d 2ed d − 1 + 2e ²



 ,

we can say that the counter-identity matrix J is in L if d = 1 and e = 0. We rewrite the J k in this case:

J 1 =





1 0 0 0 1 0 0 0 1



 , J 2 =





0 1 0

1/2 0 1/2

0 1 0



 , J 3 =





0 0 1 0 1 0 1 0 0



 .

Note that the eigenvalues of J 2 = X must be real and distinct (see the theory

on eigenstructure of tridiagonal matrices). It is easy to obtain them: −1, 0, 1.

(2)

Let us generalize this example. Let X be a generic non-derogatory tridiagonal matrix with e ^T ₂ = [0 1 0 · · · 0] as first row. Then the following result holds:

If e ^T ₁ J s = e ^T _s , s = 1, . . . , k, then e ^T ₁ J k+1 = e ^T _k+1 iff the k-th row of X is [· · · 0 ¹ 2 0 ¹ ₂ 0 · · ·]

In fact, e ^T

1 J k+1 = e ^T ₁ T k (X) = e ^T ₁ (2T k −1 (X)X − T ^k −2 (X)) = e ^T ₁ (2J k X − J ^k −1 )

= 2e ^T _k X − e ^T k −1 = [· · · 0 2x ^kk −1 − 1 2x ^kk 2x kk+1 0 · · ·].

So, for

X =







0 1 0 · · · 0

1 2 0 ¹ ₂ . .. . ..

1 2 0 ¹ ₂ a b





 we have e ^T ₁ J k = e ^T _k , k = 1, . . . , n, i.e. A = P n

k=1 a k J k means e ^T ₁ A = [a 1 a 2 . . . a n ].

Moreover, J is a polynomial in X or, equivalently, J n = J iff a = 1, b = 0 (proof:

use the identity JX = XJ).

Now assume a = 1, b = 0. In this case the J k have the form:

J k =







1

1 2 0 ¹ ₂ . . .

. . . ₁

2 . .. ...

1 2 0 . . . . .. ... ¹ ₂

1 2

1 2 0 ¹ ₂

. .. 0 ¹ ₂

. . . 1





 .

Moreover, the eigenvalues of J 2 = X must be real and distinct (see the theory on eigenstructure of tridiagonal matrices). By using this fact one can obtain them in explicit form. They are cos(jπ/(n − 1)), j = 0, . . . , n − 1.

Let us see why. Since T n −1 (X) = J n = J we have the equality T n −1 (X) ² = I.

Now, if Xv = λv then v = T n −1 (X) ² v = T n −1 (λ) ² v , in other words the eigenvalues λ of X must be zeros of the algebraic equation T n −1 (x) ² = 1. For x ∈ [−1, 1] this equation becomes cos ² ((n − 1) arccos x) = 1 whose zeros are:

x = cos(2kπ/(n − 1)) and x = cos((2k + 1)π/(n − 1)), k ∈ Z.

Eigenvectors of X ? Look for x j such that x 2 = cos _n ^jπ ₋₁ x 1 1

2 (x 1 + x 3 ) = cos _n ^jπ ₋₁ x 2

· · ·

1 2 (x n −2 + x n ) = cos _n ^jπ ₋₁ x n −1

x n −1 = cos _n ^jπ ₋₁ x n

The eigenvectors of 1 and −1 are [1 1 · · · 1] and [1 − 1 1 · · · (−1) ⁿ ⁻¹ ],

(3)

respectively. For n = 3 and n = 4:





0 1 0

1 2 0 ¹ ₂ 0 1 0









1 1 1

1 0 −1

1 −1 1



 =





1 1 1

1 0 −1

1 −1 1







 1

0 −1



 ,







0 1 0 0

1 2 0 ¹ ₂ 0 0 ¹ ₂ 0 ¹ ₂

0 0 1 0













1 1 1 1

1 ¹ ₂ − ¹ 2 −1 1 − ¹ 2 − ¹ 2 1

1 −1 1 −1







=







1 1 1 1

1 ¹ ₂ − ¹ 2 −1 1 − ¹ 2 − ¹ 2 1

1 −1 1 −1











 1

1 2

− ¹ 2

−1





 For a generic n ?

How Chebycev polynomials arise

Set y(x) = x ⁿ − p ⁿ −1 (x) where p n −1 is the unique degree-(n − 1) polynomial solving the minimum problem min p ∈P

ⁿ−1

max _[−1,1] |x ⁿ − p(x)|. If µ = max _[−1,1] |y(x)| then y(x) assumes the values µ and −µ alternately in n + 1 successive points {x i } ⁿ i=0 of [−1, 1], −1 ≤ x 0 < x 1 < x 2 < . . . < x n −1 < x n ≤ 1 (see min-max approximation theory []). Obviously y ⁰ (x i ) = 0, i = 1, . . . , n − 1, whereas y ⁰ (x 0 )y ⁰ (x n ) 6= 0 since y ⁰ (x) is a polynomial of degree n − 1. Thus x 0 = −1, x ⁿ = 1. Consider now the function y(x) ² − µ ² . It is zero in all the x i and its derivative, 2y(x)y ⁰ (x), is zero in x 1 , x 2 , . . . , x n −1 . It follows that y(x) ² −µ ² = c(x ² −1)y ⁰ (x) ² for some real constant c. Noting that the coefficient of x ²ⁿ is on the left 1 and on the right cn ² we conclude that

n ²

1 − x ² = y ⁰ (x) ²

µ ² − y(x) ² , n

√ 1 − x ² = ± y ⁰ (x) pµ ² − y(x) ² , y(x) = µ cos(n arccos x + c). Finally, y(1) = ±µ ⇒ c = kπ ⇒

y(x) = x ⁿ − p ⁿ −1 (x) = ±µ cos(n arccos x) =: ±µT ⁿ (x).

Properties of Chebycev polynomials

• T ^k (λ)| [−1,1] = cos(k arccos λ)

• T ^k (λ) = ¹ ₂ [(λ − √

λ ² − 1) ^k + (λ + √

λ ² − 1) ^k ]

• |T ^k (λ)| ≤ 1, λ ∈ [−1, 1]

• T ^k (cos ^iπ _k ) = (−1) ⁱ , i = 0, 1, . . . , k

• T ^k (cos ^(2j+1)π _2k ) = 0, j = 0, 1, . . . , k − 1

• T k (λ) ≥ λ ^k , λ ≥ 1

• T ^k ( ^λ+1 _λ ₋₁ ) = ¹ ₂ [( ^√ ^√ ^λ+1 _λ

−1 ) ^k + ( ^√ ^√ ^λ _λ+1 ⁻¹ ) ^k ], λ > 1

• T ^k ( ^λ+1 _λ ₋₁ ) > ¹ ₂ ( ^√ √ ^λ+1

λ −1 ) ^k , λ > 1

• 0 < a < b and t ^k (λ) = T k ((b + a − 2λ)/(b − a))/T ^k ((b + a)/(b − a)) imply min max

[a,b] |p k (λ)| = max

[a,b] |t k (λ)| = 1

T k ((b + a)/(b − a))

where the min is taken on all polynomials of type a k λ ^k + . . . + a 1 λ + 1,

a k 6= 0

(4)

• T k+j (λ) + T _|k−j| (λ) = 2T k (λ)T j (λ)

• R 1

−1

√ 1

1−λ

²

T k (λ)T j (λ)dλ = π, π/2, 0, j = k = 0, j = k > 0, j 6= k Chebycev as characteristic polynomials

Write a semi-infinite matrix X = [x ij ] ^+∞ _i,j=1 with the property: for all n the characteristic polynomial p n (λ) of the upper left n × n submatrix of X (X ⁿ ) is T _n ^∗ (λ) = T n (λ)/(2 ⁿ ⁻¹ ) where T n (λ) is the degree n Chebycev polynomial defined by ().

For the following choices of X,

X =







0 1/ √

2 0 0 · · · 1/ √

2 0 1/2 0 · · ·

0 1/2 0 . ..

0 0 . .. ...

.. . .. .





 , X =







0 1 0 0 · · ·

1/2 0 1/2 0 · · · 0 1/2 0 . ..

0 0 . .. ...

.. . .. .





 ,

X =







0 1 0 0 · · ·

1/2 0 1 0 · · · 0 1/4 0 . ..

0 0 . .. ...

.. . .. .





 ,

we have p 0 (λ) = 1, p 1 (λ) = λ = T 1 (λ), p 2 (λ) = λ ² − ¹ ₂ = ¹ ₂ (2λ ² − 1) = ¹ ₂ T 2 (λ), p 3 (λ) = λ(λ ² − ¹ ₂ ) − ¹ ₄ λ = λ ³ − ³ ₄ λ = ¹ ₄ (4λ ³ − 3λ) = ¹ ₄ T 3 (λ), . . ., p n (λ) = λp n −1 (λ) − ¹ ₄ p n −2 (λ) = ₂

ⁿ

¹

−1

T n (λ), . . ..

Proof: By induction:

1

2

ⁿ⁻¹

T n (λ) = ₂

ⁿ

¹

−1

(2T n −1 (λ)λ − T ⁿ −2 (λ)) = ₂

ⁿ

¹

−1

(2 · 2 ⁿ ⁻² p n −1 (λ)λ − 2 ⁿ ⁻³ p n −2 (λ))

= p n −1 (λ)λ − 2 ⁻² p n −2 (λ) = p n (λ)

Notice that the third choice of X implies e ^T ₁ p k (X n ) = e ^T _k+1 , k = 0, . . . , n − 1 . . . for all three choices of X n we refer to L, the set of all polynomials in X ⁿ , as Chebycev algebras . . . Each X is equal to DXD ⁻¹ for another X; since p(DXD ⁻¹ ) = Dp(X)D ⁻¹ from the eigenvectors v of one algebra we have easily the eigenvectors of the other algebras, they are Dv

SVD of A ∈ C ⁿ ^×n and how to compute the singular values of A ∈ R ⁿ ^×n If A is a n × n normal matrix then there exist matrices U, D, U unitary, D = diag (λ i ) with |λ 1 | ≥ |λ 2 | ≥ . . . ≥ |λ ⁿ | ≥ 0, such that A = UDU ^∗ . It follows that A admits the following singular value decomposition

A = U diag (|λ ⁱ |) diag (e ^{i arg(λ}

ⁱ

⁾ )U ^∗ = U σV ^∗ , σ = diag (σ i ), σ i = |λ ⁱ |, V = U diag (e ^{−i arg(λ}

ⁱ

⁾ ).

However, any n × n matrix A admits a singular value decomposition, i.e. there exist unitary matrices U, V and σ = diag (σ i ) with σ 1 ≥ σ 2 ≥ . . . ≥ σ ⁿ ≥ 0 such that A = U σV ^∗ . The σ i are the singular values of A.

Example. For n = 1 we have a 11 = 1 · |a 11 |(e ^{−i arg(a}

¹¹

⁾ ) ^∗ .

(5)

Proof . . .

By knowing the SVD of A we can do many things. In particular we have (0) | det(A)| = Q n

i=1 σ i

(1) σ r+1 = kA − P r

i=1 σ i u _i v ∗

i k ² = min{kA − Bk ² : rank(B) ≤ r}

(2) q P n

j=r+1 σ ² _j = kA − P r

i=1 σ i u _i v ∗

i k ^F = min{kA − Bk ^F : rank(B) ≤ r}

(3) σ n = kA − P n −1

i=1 σ i u _i v ^∗ _i k 2 = min{kA − Bk 2 : rank(B) ≤ n − 1} = min{kA − Bk 2 : det(B) = 0}

(4) kAk ² = σ 1 , kAk ^F = pP n i=1 σ ² _i

(5) σ ₁ ² , σ ₂ ² , . . . , σ _n ² are the eigenvalues of A ^∗ A

(6) det(A) 6= 0 ⇒ kA ⁻¹ k ² = 1/σ n , µ 2 (A) = σ 1 /σ n , µ 2 (A ^∗ A) = µ 2 (A) ² (7) If λ i are the eigenvalues of A, then σ n ≤ |λ ⁱ | ≤ σ ¹ . If A is normal then

σ i = |λ i |

(8) If σ 1 ≥ . . . ≥ σ ^k > 0 = σ k+1 = . . . = σ n then the kernel and the image of A can be represented as follows: {x ∈ C ⁿ : Ax = 0} = Span {v k+1 , . . . , v n }, {Ax : x ∈ C ⁿ } = Span {u 1 , . . . , u k }

How to compute U, σ, V such that A = U σV ^∗ ? An algorithm that works for A real (note that in this case U, V can be chosen real unitary (orthonormal)) consists in the following two steps (1) and (2):

Step (1). Transform A into a bidiagonal matrix

QAZ = B =





 a 1 b 1

0 a 2 b 2

. .. ...

. .. b n −1

a n







by using orthonormal transforms Q and Z.

For n = 1: 1 · a ¹¹ · 1 = a ¹¹ .

For n = 2, if α = a 11 /pa ² ₁₁ + a ² ₂₁ , β = −a 21 /pa ² ₁₁ + a ² ₂₁ , then

α −β

β α

a 11 a 12

a 21 a 22

1 0 0 1

=

αa 11 − βa 21 αa 12 − βa 22

βa 11 + αa 21 βa 12 + αa 22

=





pa ² ₁₁ + a ² ₂₁ ^a

¹¹

√ ^a

¹²

^+a

²¹

^a

²²

a

²₁₁

+a

²₂₁

0 ^−a

²¹

√ ^a

¹²

^+a

¹¹

^a

²²

a

²₁₁

+a

²₂₁



 . For n > 2 . . . example, n = 4:

A =













, S ₁₂ ^T A =







0 





,

(6)

S ₁₃ ^T (S ₁₂ ^T A) =







0

0 





, S ₁₄ ^T (S ₁₃ ^T S ₁₂ ^T A) =







0

0 



 ,

(S ₁₄ ^T S ₁₃ ^T S ₁₂ ^T A)S 23 =







0

0 





, (S ₁₄ ^T S ₁₃ ^T S ₁₂ ^T AS 23 )S 24 =







0 0

0

0 



 ,

S ₂₃ ^0T (S ₁₄ ^T S ₁₃ ^T S ₁₂ ^T AS 23 S 24 ) =







0 0

0 0 0

0 





, S ^0T ₂₄ (S ₂₃ ^0T S ₁₄ ^T S ₁₃ ^T S ₁₂ ^T AS 23 S 24 ) =







0 0

0 0 0

0 0





 ,

(S ₂₄ ^0T S ₂₃ ^0T S ^T ₁₄ S ₁₃ ^T S ₁₂ ^T AS 23 S 24 )S 34 =







0 0





 ,

S ₃₄ ^0T (S ₂₄ ^0T S ₂₃ ^0T S ₁₄ ^T S ₁₃ ^T S ₁₂ ^T AS 23 S 24 S 34 ) =







0 0

0 0 0







= B.

Thus B = QAZ, Q = S ₃₄ ^0T S ₂₄ ^0T S ₂₃ ^0T S ₁₄ ^T S ₁₃ ^T S ₁₂ ^T , Z = S 23 S 24 S 34 (Q ^T = Q ⁻¹ , Z ^T = Z ⁻¹ ). Note that the Givens transformations (plane rotations)

S ij = S ji =





 I

α β

I

−β α

I







, α ² + β ² = 1,

used to liquidate the not-on-bidiagonal-part entries are chosen so that they leave unchanged the previously posed zeros. Moreover, S ij is used to liquidate (i, j), i > j, when multiplying on the left, and S i+1j is used to liquidate (i, j), i < j −1, when multiplying on the right.

Exercise (Elisa Sallicandro). Transform the matrix

A =







1 0 2 0

−1 1 0 0

0 0 −1 3

4 0 0 1





 into a bidiagonal matrix B.

Step (2). Set A 1 := B and define a sequence of matrices {A j } ^+∞ j=1 via the rule: for k = 2, 4, 6, . . .

A k −1 =







a ^k ₁ ⁻¹ b ^k ₁ ⁻¹ 0 a ^k ₂ ⁻¹ . ..

. .. b ^k _n ⁻¹ ₋₁ a ^k _n ⁻¹







→ A ^k = A k −1 Z k −1 =





 a ^k ₁ b ^k ₁ a ^k ₂

. .. ...

b ^k n −1 a ^k n







(7)

(Z k −1 is the product of the n − 1 plane rotations used to liquidate the entries (i, i + 1) of A k −1 ),

A k → A ^k+1 = Q k A k =







a ^k+1 ₁ b ^k+1 ₁ 0 a ^k+1 ₂ . ..

. .. b ^k+1 _n ₋₁ a ^k+1 _n







(Q k is the product of the n − 1 plane rotations used to liquidate the entries (i + 1, i) of A k ).

Then b ^j _i → 0 if j → +∞ (i = 1, . . . , n − 1). (Question: one should also prove that the a ^j _i , i = 1, . . . , n, have non-negative limit)

Proof: Let us show that b ^j _n ₋₁ → 0 if j → +∞.

The euclidean norm of the i-th column of A k is equal to the euclidean norm of the i-th column of A k+1 . Thus

a 1 (k) ² + b 1 (k) ² = a 1 (k + 1) ²

b 2 (k) ² + a 2 (k) ² = a 2 (k + 1) ² + b 1 (k + 1) ²

· · ·

a n (k) ² = a n (k + 1) ² + b n −1 (k + 1) ²

Moreover, the euclidean norm of the n-th row of A k −1 is equal to the euclidean norm of the n-row of A k . Thus

kBk ² F = kA ^k+1 k ² F ≥ a ⁿ (k + 1) ² = a n (k − 1) ² − b ⁿ −1 (k + 1) ² − b ⁿ −1 (k) ²

= . . . = a n (1) ² − P k+1

j=2 b n −1 (j) ² ≥ 0.

But this implies P +∞

j=1 b n −1 (j) ² < +∞, and we have the thesis.

(b ^j n −2 → 0: The euclidean norm of the (n − 1)-th row of A ^k −1 is equal to the euclidean norm of the (n − 1)-th row of A ^k . Thus

a n −1 (k + 1) ² = a n −1 (1) ² +

k

X

j=1

b n −1 (j) ² −

k+1

X

j=2

b n −2 (j) ²

⇒ P +∞

j=1 b n −2 (j) ² < +∞ ⇒ b ⁿ −2 (j) → 0 if j → ∞. . . .) Step (2) for n = 2 (convergence).

A k −1 =

a ^k ₁ ⁻¹ b ^k ₁ ⁻¹ 0 a ^k ₂ ⁻¹

→ A ^k = A k −1 Z k −1 =

a ^k ₁ 0 b ^k ₁ a ^k ₂

→ A ^k+1 = Q k A k =

a ^k+1 ₁ b ^k+1 ₁ 0 a ^k+1 ₂

, kA ^k e _i k 2 = kA k+1 e _i k 2 ⇒

a 1 (k) ² + b 1 (k) ² = a 1 (k + 1) ² , a 2 (k) ² = b 1 (k + 1) ² + a 2 (k + 1) ² ,

kA ^T k −1 e ₂ k 2 = kA ^T k e ₂ k 2 ⇒ a 2 (k − 1) ² = b 1 (k) ² + a 2 (k) ² . Thus

kBk ² F = kA ^k+1 k ² F ≥ a ² (k + 1) ² = a 2 (k − 1) ² − b ¹ (k) ² − b ¹ (k + 1) ²

= a 2 (1) ² − P k+1

j=2 b 1 (j) ² ⇒ b 1 (j) → 0.

(8)

Step (2) for n = 2 (details and example). Given an upper triangular (bidiagonal) 2 × 2 matrix

A =

a 1 b 1

0 a 2

,

write an algorithm to compute its singular values σ 1 , σ 2 . (Notice however that σ 1 , σ 2 are simply the squaring roots of the eigenvalues of

a 1 0 b 1 a 2

a 1 b 1

0 a 2

=

|a ¹ | ² a 1 b 1

b 1 a 1 |b ¹ | ² + |a ² | ²

, i.e.

q 1

2 (|a 1 | ² + |a 2 | ² + |b 1 | ² ± p(|a 1 | ² + |a 2 | ² + |b 1 | ² ) ² − 4|a 1 | ² |a 2 | ² ) ).

Solution. Set A 1 = A and, for k = 2, 4, . . . Z k −1 =

α β

−β α

, α = a 1

pa ² ₁ + b ² ₁ , β = −b 1

pa ² ₁ + b ² ₁ . Then

A k = A k −1 Z k −1 =

a 1 α − b 1 β a 1 β + b 1 α

−a 2 β a 2 α

=

"

pa ² ₁ + b ² ₁ 0

a

2

b

1

√ a

²₁

+b

²₁

a

2

a

1

√ a

²₁

+b

²₁

# . Now set

Q k =

α −β

β α

, α = pa ² ₁ + b ² ₁ q

a ² ₁ + b ² ₁ + _a ^a

2²²

^b

²¹ 1

+b

²₁

, β =

−a

²

b

1

√ a

²₁

+b

²₁

q

a ² ₁ + b ² ₁ + _a ^a

2²²

^b

²¹ 1

+b

²₁

.

Then

A k+1 = Q k A k = Q k A k −1 Z k −1

=





αpa ² ₁ + b ² ₁ − β √ ^a

²

^b

¹

a

²₁

+b

²₁

−β √ ^a

²

^a

¹

a

²₁

+b

²₁

βpa ² ₁ + b ² ₁ + α √ ^a

²

^b

¹

a

²₁

+b

²₁

α √ ^a

²

^a

¹

a

²₁

+b

²₁





=







q a ² ₁ + b ² ₁ + _a ^a

2²²

^b

²¹ 1

+b

²₁

a

²₂

a

1

b

1

(a

²₁

+b

²₁

) r

a

²₁

+b

²₁

+

_a2^a2²^b2¹

1+b2 1

0 r ^a

²

^a

¹

a

²₁

+b

²₁

+

^a2²^b2¹

a21+b21





 .

The algorithm

10 a 1 =? a 2 =? b 1 =?

20 a ^new ₁ = q

a ² ₁ + b ² ₁ + _a ^a

2²²

^b

²¹ 1

+b

²₁

30 a ^new ₂ = r ^a

²

^a

¹

a

²₁

+b

²₁

+

_a2^a2²^b2¹

1+b2 1

40 b ^new ₁ = ^a

²²

^a

¹

^b

¹

(a

²₁

+b

²₁

) r

a

²₁

+b

²₁

+

_a2^a2²^b2¹

1+b2 1

50 a 1 = a ^new ₁ ; a 2 = a ^new ₂ ; b 1 = b ^new ₁ ; GOTO 20

should generate a sequence of b 1 convergent to 0, and sequences of a 1 and a 2 convergent to the singular values. (Note that a ^k+1 ₁ a ^k+1 ₂ = | det(A k+1 )| =

| det(A ^k −1 )| = | det(A)| = σ 1 σ 2 = a 1 a 2 ).

(9)

An implementation of the algorithm:

a 1 =?; a 2 =?; b 1 =?

20 x = a ² ₁ + b ² ₁ y = a 2 b 1

z = a 2 a 1

b ^new ₁ = y/x

a ^new ₁ = px + y ∗ b ^new 1

a ^new ₂ = z/a ^new ₁ b ^new ₁ = b ^new ₁ ∗ a ^new 2

a 1 = a ^new ₁ ; a 2 = a ^new ₂ ; b 1 = b ^new ₁ ; GOTO 20 Example. If a 1 = a 2 = 1, b 1 = −1, then

σ 1 = s

3 + √ 5 2 , σ 2 =

s 3 − √

5 2 .

Let us do some steps of the proposed algorithm. (Note that a ^k+1 ₁ a ^k+1 ₂ =

| det(A ^k+1 )| = | det(A ^k −1 )| = | det(A)| = σ ¹ σ 2 = 1).

a 1 1 q

5 2

q 34 13

a 2 1 q

2 5

q 13 34

b 1 −1 − ^√ ¹ ₁₀ − ^√ _13·34 ¹ x = a ² ₁ + b ² ₁ 2 ¹³ ₅ ⁸⁹ ₃₄

y = a 2 b 1 −1 − ¹ ₅ − ₃₄ ¹

z = a 2 a 1 1 1 1

b ^new ₁ = y/x − ¹ ₂ − ₁₃ ¹ − ₈₉ ¹ a ^new ₁ = px + y ∗ b ^new 1

q 5 2

q 34 13

q 233 89

a ^new ₂ = z/a ^new ₁ q

2 5

q 13 34

q 89 233

b ^new ₁ = b ^new ₁ ∗ a ^new 2 − ^√ ¹ ₁₀ − ^√ _13·34 ¹ − ^√ _89·233 ¹

We should have a 1 → σ 1 , a 2 → σ 2 , b 1 → 0, and this is the case: for instance we have ⁵ ₂ = 2.5, ³⁴ ₁₃ = 2.615, ²³³ ₈₉ = 2.6179, . . . → σ 1 ² = 2.61803 ( √

5 ≈ 2.23607).

T 0 (x) = 1, T 1 (x) = x, T k (x) = 2T k −1 (x)x − T k −2 (x), k = 2, 3, . . . , and recall their alternative representation in [−1, 1]

A new matrix algebra ?

Let T j (x) be the Chebycev polynomials