Fundamentals of Linear Algebra and Optimization Homework 4 + Project 2

Problem B1 (40 pts). Let A be an n?n matrix which is strictly row diagonally dominant, which means that jai ij
X
j6=i
jai j j;
for i = 1 : : : ; n, and let
? = min
i
?
jai ij 􀀀
X
j6=i
jai j j
?
:
The fact that A is is strictly row diagonally dominant is equivalent to the condition ? 0.
(1) For any nonzero vector v, prove that
kAvk1 ? kvk1 ?:
Use the above to prove that A is invertible.
(2) Prove that
A􀀀1

1
? ?􀀀1:
Hint. Prove that
sup
v6=0
kA􀀀1vk1
kvk1
= sup
w6=0
kwk1
kAwk1
:
Problem B2 (20 pts). Let A be any invertible complex n ? n matrix.
(1) For any vector norm k k on Cn, prove that the function k kA : Cn ! R given by
kxkA = kAxk for all x 2 Cn; is a vector norm.
(2) Prove that the operator norm induced by k kA, also denoted by k kA, is given by
kBkA =

ABA􀀀1

for every n ? n matrix B; where kABA􀀀1k uses the operator norm induced by k k.

Problem B3 (80 pts). (1) Implement the method for converting a rectangular matrix to reduced row echelon fom.
(2) Use the above method to ?nd the inverse of an invertible n?n matrix A, by applying it to the the n?2n matrix [AI] obtained by adding the n columns of the identity matrix to A.
(3) Consider the matrix
A = 0
BBBBB@
1 2 3 4 ? ? ? n
2 3 4 5 ? ? ? n + 1
3 4 5 6 ? ? ? n + 2
...
...
...
. . .
...
n n + 1 n + 2 n + 3 ? ? ? 2n 􀀀 1
1
CCCCCA
:
Using your program, ?nd the row reduced echelon form of A for n = 4; : : : ; 20.
Also run the Matlab rref function and compare results.
Your program probably disagrees with rref even for small values of n. The problem is that some pivots are very small and the normalization step (to make the pivot 1) causes roundo? errors. Use a tolerance parameter to ?x this problem.
What can you conjecture about the rank of A?
(4) Prove that the matrix A has the following row reduced form:
R = 0
BBBBB@
1 0 􀀀1 􀀀2 ? ? ? 􀀀(n 􀀀 2)
0 1 2 3 ? ? ? n 􀀀 1
0 0 0 0 ? ? ? 0
...
...
...
. . .
...
0 0 0 0 ? ? ? 0
1
CCCCCA
:
Deduce from the above that A has rank 2.
Hint. Some well chosen sequence of row operations.
(5) Use your program to show that if you add any number greater than or equal to
(2=25)n2 to every diagonal entry of A you get an invertible matrix! In fact, running the Matlab fuction chol should tell you that these matrices are SPD (symmetric, positive de?nite).
Remark: The above phenomenon will be explained in Problem B4. If you have a rigorous and simple explanation for this phenomenon, let me know!
2
Problem B4 (120 pts). The purpose of this problem is to prove that the characteristic polynomial of the matrix
A = 0
BBBBB@
1 2 3 4 ? ? ? n
2 3 4 5 ? ? ? n + 1
3 4 5 6 ? ? ? n + 2
...
...
...
. . .
...
n n + 1 n + 2 n + 3 ? ? ? 2n 􀀀 1
1
CCCCCA
is
PA(?) = ?n􀀀2
?
?2 􀀀 n2? 􀀀
1
12
n2(n2 􀀀 1)
?
:
(1) Prove that the characteristic polynomial PA(?) is given by PA(?) = ?n􀀀2P(?);
with
P(?) = ? 􀀀 1 􀀀2 􀀀3 􀀀4 ? ? ? 􀀀n + 3 􀀀n + 2 􀀀n + 1 􀀀n
􀀀? 􀀀 1 ? 􀀀 1 􀀀1 􀀀1 ? ? ? 􀀀1 􀀀1 􀀀1 􀀀1
1 􀀀2 1 0 ? ? ? 0 0 0 0
0 1 􀀀2 1 ? ? ? 0 0 0 0
...
...
. . . . . . . . .
...
... ...
...
0 0 0 0
. . . 1 0 0 0
0 0 0 0
. . . 􀀀2 1 0 0
0 0 0 0 ? ? ? 1 􀀀2 1 0
0 0 0 0 ? ? ? 0 1 􀀀2 1

:
(2) Prove that the sum of the roots ?1; ?2 of the (degree two) polynomial P(?) is
?1 + ?2 = n2:
The problem is thus to compute the product ?1?2 of these roots. Prove that
?1?2 = P(0):

(3) The problem is now to evaluate dn = P(0), where
dn = 􀀀1 􀀀2 􀀀3 􀀀4 ? ? ? 􀀀n + 3 􀀀n + 2 􀀀n + 1 􀀀n
􀀀1 􀀀1 􀀀1 􀀀1 ? ? ? 􀀀1 􀀀1 􀀀1 􀀀1
1 􀀀2 1 0 ? ? ? 0 0 0 0
0 1 􀀀2 1 ? ? ? 0 0 0 0
...
...
. . . . . . . . .
...
...
...
...
0 0 0 0
. . . 1 0 0 0
0 0 0 0
. . . 􀀀2 1 0 0
0 0 0 0 ? ? ? 1 􀀀2 1 0
0 0 0 0 ? ? ? 0 1 􀀀2 1

I suggest the following strategy: cancel out the ?rst entry in row 1 and row 2 by adding a suitable multiple of row 3 to row 1 and row 2, and then subtract row 2 from row 1.
Do this twice.
You will notice that the ?rst two entries on row 1 and the ?rst two entries on row 2
change, but the rest of the matrix looks the same, except that the dimension is reduced.
This suggests setting up a recurrence involving the entries uk; vk; xk; yk in the determinant
Dk = uk xk 􀀀3 􀀀4 ? ? ? 􀀀n + k 􀀀 3 􀀀n + k 􀀀 2 􀀀n + k 􀀀 1 􀀀n + k
vk yk 􀀀1 􀀀1 ? ? ? 􀀀1 􀀀1 􀀀1 􀀀1
1 􀀀2 1 0 ? ? ? 0 0 0 0
0 1 􀀀2 1 ? ? ? 0 0 0 0
...
...
. . . . . . . . .
...
...
...
...
0 0 0 0
. . . 1 0 0 0
0 0 0 0
. . . 􀀀2 1 0 0
0 0 0 0 ? ? ? 1 􀀀2 1 0
0 0 0 0 ? ? ? 0 1 􀀀2 1

;
starting with k = 0, with
u0 = 􀀀1; v0 = 􀀀1; x0 = 􀀀2; y0 = 􀀀1;
and ending with k = n 􀀀 2, so that
dn = Dn􀀀2 =

un􀀀3 xn􀀀3 􀀀3
vn􀀀3 yn􀀀3 􀀀1
1 􀀀2 1

=

un􀀀2 xn􀀀2
vn􀀀2 yn􀀀2

:

Prove that we have the recurrence relations
0
BB@
uk+1
vk+1
xk+1
yk+1
1
CCA
=
0
BB@
2 􀀀2 1 􀀀1
0 2 0 1
􀀀1 1 0 0
0 􀀀1 0 0
1
CCA
0
BB@
uk
vk
xk
yk
1
CCA
+
0
BB@
0
0
􀀀2
􀀀1
1
CCA
:
These appear to be nasty a?ne recurrence relations, so we will use the trick to convert this a?nd map to a linear map.
(4) Consider the linear map given by
0
BBBB@
uk+1
vk+1
xk+1
yk+1
1
1
CCCCA
=
0
BBBB@
2 􀀀2 1 􀀀1 0
0 2 0 1 0
􀀀1 1 0 0 􀀀2
0 􀀀1 0 0 􀀀1
0 0 0 0 1
1
CCCCA
0
BBBB@
uk
vk
xk
yk
1
1
CCCCA
;
and show that its action on uk; vk; xk; yk is the same as the a?ne action of part (3).
Use Matlab to ?nd the eigenvalues of the matrix
T =
0
BBBB@
2 􀀀2 1 􀀀1 0
0 2 0 1 0
􀀀1 1 0 0 􀀀2
0 􀀀1 0 0 􀀀1
0 0 0 0 1
1
CCCCA
:
You will be stunned!
Let N be the matrix given by
N = T 􀀀 I:
Prove that N4 = 0:
Use this to prove that
Tk = I + kN +
1
2
k(k 􀀀 1)N2 +
1
6
k(k 􀀀 1)(k 􀀀 2)N3;
for all k ? 0.
(5) Prove that
0
BBBB@ uk
vk
xk
yk
1
1
CCCCA
= Tk
0
BBBB@
􀀀1
􀀀1
􀀀2
􀀀1
1
1
CCCCA
=
0
BBBB@
2 􀀀2 1 􀀀1 0
0 2 0 1 0
􀀀1 1 0 0 􀀀2
0 􀀀1 0 0 􀀀1
0 0 0 0 1
1
CCCCA
k 0
BBBB@
􀀀1
􀀀1
􀀀2
􀀀1
1
1
CCCCA
;
5
for k ? 0.
Prove that
Tk =
0
BBBBBBB@
k + 1 􀀀k(k + 1) k 􀀀k2 1
6 (k 􀀀 1)k(2k 􀀀 7)
0 k + 1 0 k 􀀀1
2 (k 􀀀 1)k
􀀀k k2 k 􀀀 1 (k 􀀀 1)k 􀀀1
3k((k 􀀀 6)k + 11)
0 􀀀k 0 k 􀀀 1 1
2 (k 􀀀 3)k
0 0 0 0 1
1
CCCCCCCA
;
and thus, that 0
BBBB@
uk
vk
xk
yk
1
CCCCA
=
0
BBBB@
1
6(2k3 + 3k2 􀀀 5k 􀀀 6)
􀀀1
2 (k2 + 3k + 2)
1
3 (􀀀k3 + k 􀀀 6)
1
2 (k2 + k 􀀀 2)
1
CCCCA
;
and that ???? uk xk
vk yk

= 􀀀1 􀀀
7
3
k 􀀀
23
12
k2 􀀀
2
3
k3 􀀀
1
12
k4:
As a consequence, prove that amazingly, dn = Dn􀀀2 = 􀀀
1
12
n2(n2 􀀀 1):
(6) Prove that the characteristic polynomial of A is indeed
PA(?) = ?n􀀀2
?
?2 􀀀 n2? 􀀀
1
12
n2(n2 􀀀 1)
?
:
Use the above to show that the two nonzero eigenvalues of A are
? = n
2

n ?
p
3
3
p
4n2 􀀀 1
!
:
The negative eigenvalue ?1 can also be expressed as
?1 = n2 (3 􀀀 2
p
3)
6
r
1 􀀀
1
4n2 :
Use this expression to explain the phenomenon in B3(5): If we add any number greater than or equal to (2=25)n2 to every diagonal entry of A we get an invertible matrix. What about 0:077351n2? Try it!
6
Problem B5 (40 pts). A method for computing the nth root x1=n of a positive real number x 2 R, with n 2 N a positive integer n ? 2, proceeds as follows: De?ne the sequence (xk), where x0 is any chosen positive real, and
xk+1 =
1
n
?
(n 􀀀 1)xk +
x
xn􀀀1
k
?
; k ? 0:
(1) Implement the above method in Matlab, and test it for various input values of x, x0, and of n ? 2, by running successively your program for m = 2; 3; : : : ; 100 iterations. Have your program plot the points (i; xi) to watch how quickly the sequence converges.
Experiment with various choices of x0. One of these choices should be x0 = x. Compare your answers with the result of applying the of Matlab function x 7! x1=n.
In some case, when x0 is small, the number of iterations has to be at least 1000. Exhibit this behavior.
Problem B6 (80 pts). Refer to Problem B5 for the de?nition of the sequence (xk).
(1) De?ne the relative error ?k as
?k =
xk
x1=n
􀀀 1; k ? 0:
Prove that
?k+1 =
x(1􀀀1=n)
nxn􀀀1
k
?
(n 􀀀 1)xnk
x
􀀀
nxn􀀀1
k
x(1􀀀1=n) + 1
?
;
and then that
?k+1 =
1
n(?k + 1)n􀀀1
􀀀
?k(?k + 1)n􀀀2((n 􀀀 1)?k + (n 􀀀 2)) + 1 􀀀 (?k + 1)n􀀀2?
;
for all k ? 0.
(2) Since ?k + 1 = xk
x1=n ;
and since we assumed x0; x 0, we have ?0 + 1 0. We would like to prove that
?k ? 0; for all k ? 1:
For this, consider the variations of the function f given by
f(u) = (n 􀀀 1)un 􀀀 nx1=nun􀀀1 + x;
for u 2 R.

Use the above to prove that f(u) ? 0 for all u ? 0. Conclude that
?k ? 0; for all k ? 1:
(3) Prove that if n = 2, then
0 ? ?k+1 =
?2k
2(?k + 1)
; for all k ? 0;
else if n ? 3, then
0 ? ?k+1 ?
(n 􀀀 1)
n
?k; for all k ? 1:
Prove that the sequence (xk) converges to x1=n for every initial value x0 0.
(4) When n = 2, we saw in B6(3) that
0 ? ?k+1 =
?2
k
2(?k + 1)
; for all k ? 0:
For n = 3, prove that
?k+1 =
2?2
k(3=2 + ?k)
3(?k + 1)2 ; for all k ? 0;
and for n = 4, prove that
?k+1 =
3?2
k
4(?k + 1)3
􀀀
2 + (8=3)?k + ?2
k
?
; for all k ? 0:
Let ?3 and ?4 be the functions given by
?3(a) =
3
2
+ a
?4(a) = 2 +
8
3
a + a2;
so that if n = 3, then
?k+1 =
2?2
k?3(?k)
3(?k + 1)2 ; for all k ? 0;
and if n = 4, then
?k+1 =
3?2
k?4(?k)
4(?k + 1)3 ; for all k ? 0:
Prove that
a?3(a) ? (a + 1)2 􀀀 1; for all a ? 0;
and
a?4(a) ? (a + 1)3 􀀀 1; for all a ? 0:
8
Let ?3;k = ?3(?1)?k when n = 3, and ?4;k = ?4(?1)?k when n = 4. Prove that
?3;k+1 ?
2
3
?2
3;k; for all k ? 1;
and
?4;k+1 ?
3
4
?2
4;k; for all k ? 1:
Deduce from the above that the rate of convergence of ?i;k is very fast, for i = 3; 4 (and
k ? 1).
Remark: If we let ?2(a) = a for all a and ?2;k = ?k, then we proved that
?2;k+1 ?
1
2
?2
2;k; for all k ? 1:
Extra Credit (150 pt)
(5) Prove that for all n ? 2, we have
?k+1 =
?
n 􀀀 1
n
?
?2
k?n(?k)
(?k + 1)n􀀀1 ; for all k ? 0;
where ?n is given by
?n(a) =
1
2
n +
Xn􀀀4
j=1
1
n 􀀀 1
?
(n 􀀀 1)
?
n 􀀀 2
j
?
+ (n 􀀀 2)
?
n 􀀀 2
j + 1
?
􀀀
?
n 􀀀 2
j + 2
??
aj
+
n(n 􀀀 2)
n 􀀀 1
an􀀀3 + an􀀀2:
Furthermore, prove that ?n can be expressed as
?n(a) =
1
2
n +
n(n 􀀀 2)
3
a +
Xn􀀀4
j=2
(j + 1)n
(j + 2)(n 􀀀 1)
?
n 􀀀 1
j + 1
?
aj +
n(n 􀀀 2)
n 􀀀 1
an􀀀3 + an􀀀2:
(6) Prove that for every j, with 1 ? j ? n􀀀1, the coe?cient of aj in a?n(a) is less than
or equal to the coe?cient of aj in (a + 1)n􀀀1 􀀀 1, and thus a?n(a) ? (a + 1)n􀀀1 􀀀 1; for all a ? 0;
with strict inequality if n ? 3. In fact, prove that if n ? 3, then for every j, with 1 ? j ?
n􀀀2, the coe?cient of aj in a?n(a) is strictly less than the coe?cient of aj in (a+1)n􀀀1􀀀1.
Let ?n;k = ?n(?1)?k (n ? 2). Prove that
?n;k+1 ?
?
n 􀀀 1
n
?
?2
n;k; for all k ? 1:
TOTAL: 380 + 150 points.
9