Math 660 - Fall 1999

Solutions to Selected Problems

29 August

Problem 1.1.1

c=I(:,1)
d=0
for k=1:n 
    for j=1:n
        d=(A(:,j) - x(k)I(:,j))*c(j) + d
    end
    c=d
    d=o
end 

---

2 September

Problem 1.2.5.

Recall that A = A^H, and that A = B + iC, where B and C are real. B^T = B and C^T = -C. We store B and C in the array A_herm. The lower triagular part of A_herm and the diagonal coincide with B. The upper triangular part coincides with C. We want to compute the real and imaginary parts of z = Ax, given A_herm and the real and imaginary parts of x. Let r = Re(x), s = Im(x), u = Re(z), and v = Im(z). Multiplying Ax, we obtain the following:

u = Br - Cs and v = Bs + Cr.

We can compute these vectors using the information stored in the matrix A_herm :

for k=1:n

    u(k) = A.herm(k,1:k)*r(1:k) + r((k+1):n)^T *A.herm((k+1):n,k)
           + s(1:k)^T*A.herm(1:k,k) - A.herm(k,k:n)*s(k,k:n)

    v(k) = A.herm((k,1:k)*s(1:k) + s((k+1):n)^T *A.herm(((k+1):n,k)
           - r(1:k)^T *A.herm(1:k,k) + A.herm(k,k:n)*r(k,k:n)
end

---

Problem 1.2.10.

The structure of a typical matrix is (n=4)

p1 q1	p1 q2	p1 q3	p1 q4
p1 q2	p2 q2	p2 q3	p2 q4
p1 q3	p2 q3	p3 q3	p3 q4
p1 q4	p2 q4	p3 q4	p4 q4

Here is an algorithm for computing the product of Ax, where A has the form given.

a=0
b=q*x (2*n flops)
for j=1:n,
    a = a + p(j)*x(j) (2 flops)
    b = b - q(j)*x(j) (2 flops)
    y(j) = a*q(j) + b*p(j) (3 flops)
end

There are 7 flops per iteration, so the loop takes 7*n flops. The inialization requires 2*n flops. Overall, the process takes 9*n flops.

Problem 2.5.1.

The matrix I - S will be singular if and only if there is a vector x in Rⁿ such that (I - S) x = 0. Multiply on the left by x^T to get the equation x^Tx - x^TS x = 0. Note that

x^TS x =( S^T x^T)^T x = -(S x^T)^T x = - x^T S x ==> x^TS x = 0.

Hence, x^Tx = x^TS x = 0, and x = 0. Thus, I - S is nonsingular. Similarly, I + S is nonsingular. hence,

( (I - S)^-1(I + S) )^T = (I - S) (I + S)^-1 = (I + S)^-1 (I - S),

which is the inverse of the matrix (I - S)^-1(I + S).

Formulas 2.5.1 and 2.5.2

We first deal with 2.5.1. The square of Frobenius norm ||A||_F² = Sum_{j, k} |A(j, k)|². We make the following observations.

1. ||A^T||_F² = ||A||_F², because Sum_j,k |A^T(j, k)|² = Sum_{j, k} |A(k, j)|² = Sum_{k, j} |A(k, j)|².
2. ||A||_F² = Sum_k ||A(:, k)||₂² (Sum over j gives the 2-norm of a column.)
3. For any matrix B compatible with A, B*A=[B*A(:,1) ... B*A(:,n)], so ||B*A||_F² = Sum_k ||B*A(:, k)||₂²

For Q orthogonal,
||Q*A||_F² = Sum_k ||Q*A(:, k)||₂² = Sum_k ||A(:, k)||₂² = ||A||_F²

For Z orthogonal,
|A*Z||_F² = ||(A*Z)^T||_F² = ||Z^T*A^T||_F² = ||A^T||_F² = ||A||_F²

Putting the two together gives the formula 2.5.1. The derivation for 2.5.2 is less difficult, and we will not give it here.