Problem of the Day
Here is a small problem to practice your Matlab. Each entry in a 2-by-2 matrix is randomly selected from the set {0,1,...,999}.
Estimate the probability that the matrix is singular by generating a million such matrices and counting the number that are singular.
Hint. Use help to learn about rand and floor and use the numbers in floor(rand(1000000,4)*1000)
A is m-by-n, B is n-by-p, and C is p-by-q. When is D = (A*B)*C more efficient than D = A*(B*C) from the flop point of view?
Complete the following function so that it performs as specified.
function x = SudokuCheck(A)
% A is a 9-by-9 matrix with entries selected from {1,2,3,4,5,6,7,8,9}
% Define the s-blocks of A to be A(1:3,1:3), A(1:3,4:6), A(1:3,7:9),
% A(4:6,1:3), A(4:6,4:6), A(4:6,7:9), A(7:9,1:3), A(7:9,4:6), and
% A(7:9,7:9).
% x = 1 if the entries of every row, column, and S-block sum to 45.
% x = 0 otherwise
% Strive for a SHORT implementation
% Hint: For the column and row sums, look at sum(A) and sum(A')
% For the s-blocks, look at reshape(A,3,27), rearrange the column order
% reshape again, and use sum.
B = reshape(A,3,27);
x = ???????????????????????????????????????????????????????????????????????????????????????;
FYI. My solution is just as long as the ??? string. Hint: Describe B(:,1:3:27)
in terms of the original A.
Prove that if A is n-b-n, then norm(A,2) <= n* max|A(i,j)|. Hint:
[a b c; d e f; g h k] = M1 + M2 + M3 where
M1 = [a 0 0; 0 e 0; 0 0 k], M2 = [ 0 b 0; 0 0 f; g 0 0], M3 = [0 0 c ; d 0 0; 0 h 0].
The 2 norm of each of these matrices is "easy". norm(A,2)<= norm(M1,2)+norm(M2,2)+norm(M3,2)
Given a square matrix A, find a matrix B that has a repeated singular value and satisfies norm(A-B,2) = d/sqrt(2) where d = min sigma(i)-sigma(i+1), i=1:n-1.
If A is a nonsingular n-by-n matrix and b is a given n-vector. How would you compute x and y so Ax=b and A'y = b?
If u = I(:,i) and v = I(:,j) then A = alfa*u*v' is the same as A except that the (i,j) entry is now A(i,j)+alfa. The Sherman-Morrison theorem says that A + alfa*u*v' is singular iff 1 + alfa*v'*inv(A)*u = 0.
Now suppose E is k-by-k and that A is nonsingular but n-by-n with n>>k. How can we chose alfa so that Atilde is singular where Atilde is the same as A except Atilde(1:k,1:k) = A(1:k,1:k) + alfa*E? Use the Sherman-Morrison-Woodbury formula on p. 50. Hint: express Atilde as a rank-k modification of A.
Suppose y and z are column n-vectors and that e_k is the kth column of the n-by-n identity I. Under what conditions can you find a column n-vector v so that (I - v*e_k')y = z?
Suppose pVec is a permutation of the integer vector 1:n. Let P be the n-by-n permutation matrix whose i-th row is row pVec(i) of I, the n-by-n identity. Suppose x is a column n-vector. How would you compute y = P'*x?
% Generallize this so that it handles general n...
function [L,U] = MyBlockLU(A)
% A n-by-n with n a power of two.
% Assume that A has an LU factorization
% A = L*U
[n,n] = size(A);
if n==2
L = [ 1 0 ; A(2,1)/A(1,1) 1];
U = [ A(1,1) A(1,2) ; 0 A(2,2) - A(1,2)*L(2,1)];
else
m = n/2;
% Compare blocks in ...
% L11 0 U11 U12 A11 A12
% * = (all blocks m-by-m)
% L21 L22 0 U22 A21 A22
[L11,U11] = MyBlockLU(A(1:m,1:m)); % L11*U11 = A11
U12 = L11\A(1:m,m+1:n); % L11*U12 = A12
L21 = (U11'\A(m+1:n,1:m)')'; % L21*U11 = A21
[L22,U22] = MyBlockLU(A(m+1:n,m+1:n)-L21*U12); % L21*U12 + L22*U22 = A22
L = [L11 zeros(m,m) ; L21 L22];
U = [U11 U12; zeros(m,m) U22];
end
Show that if A is nonsingular and has an LU factorization, then there exists an eps so that if norm(B-A,2)<=eps then B has an LU factorization
If we apply Gaussian Elimination with partial pivoting to a symmetric positive definite matrix A and produce PA = LU, does it follow that P = I?
If Ax = b+r then (A+E)x = b where E = -r*x'/(x'*x). Thus, if r is "small" then so is E. If A is symmetric and Ax = b+r, can you find a small symmetric F so (A+F)x = b?
Suppose H is lower Hessenberg. How would you solve Hx = b?
Suppose A is an n-by-n symmetric matrix. Let mu = max|A(i,j)| and assume that the max occurs off the diagonal. Overwrite A with B = P*A*P' where P is a permutation and |B(2,1)| = mu.
Suppose Tx = b + e where T is symmetric positive definite Toeplitz and x and b are given n-vectors. Can we find a symmetric Toeplitz E so (T + E)x = b? Hint: set up a linear system for the n-scalars that define E.
Without using the gradient, show that norm(Ax-b,2) is minimized by setting x = (A'*A)\(A'*b)
Suppose A is n-by-n. Making effective use of the Matlab QR function, i.e., {Q,R] = qr(A), show how to compute an orthogonal U and a lower triangular L so A = U*L. Hint: If E = I(:,n:-1:1), what can you say about EUE where U is upper triangular?
How would you use the Matlab QR function to compute the QR factorization of A = Y*Z' where Y and Z are m-by-n matrices with m>n.
Suppose A is m-by-n with rank(A) = r < n. How would you find the minimzer of norm(A*x-b,2) which is closest to a given vector d?
Show that x_TLS solves (A'*A - sigma*I)x = A'*b where sigma is the smallest singular value of [A b] and we assume that sigma < smallest singular value of A.
Suppose x(lambda) solves (A'*A - lambda*I)x = A'*b where A is m-by-n with rank n. If lambda_1 < lambda_2, what can you say about norm(A*x(lambda_1) - b) versus norm(A*x(lambda_2_ - b) ?
Suppose A and B are given 2-by-2 matrices. How would you minimize norm(A-BQ,'fro') subject to the constraint that Q = [c s ; -s c]? iIe., Q is a rotation
We have three n-by-n orthogonal matrices partitioned conformably:
Q = [Q1 Q2] U = [U1 U2] V = [V1 V2]
Recall the definition of distance between subspaces (Theorem 2.6.1). Show that
dist(ran(Q1),ran(V1)) <= dist(ran(Q1),ran(U1)) + dist(ran(U1),ran(V1))
Hint: I = U1*U1' + U2*U2'.
Suppose A is a 2-by-2 matrix. How would you compute the cosine-sine pair (c,s) so that if Q = [c s;-s;c] then Q'*A is symmetric. Given that you can do that, how would you compute a 2-by-2 SVD?
Suppose A is skew-symmetric. How could you compute Householder matrices P_1,...P_n-1 so that if U = P_1 *...* P_n-2, then U'*A*U is tridiagonal.
Suppose Q'*A*Q = diag(d1,...,dn) is a schur decomposition. Assume that x is a unit vector and that lambda is not an eigenvalue of A and that it is closest to dk. If z solves (A - lambda*I)z = x and y = z/norm(z), does it follow that |Q(:,k)'*y| > |Q(:,k)*x| ? That is, the angle between Q(:,k) and y is smaller than the angle between Q(:,k) and k?
If B is n-by-n and bidiagonal. By considering the tridiagonal matrix B'*B, can we conclude that the singular values of B(1:k-1,1:k-1) separate the singular values of B(1:k,1:k) for k=2:n?
Suppose A is n-by-n, symmetric, and pentadiagonal. Assume that a(1:n) is the diagonal, b(1:n-1) is the super diagonal, and c(1:n-2) is the super-super diagonal. Let p_k(x) = det(A(1:k,1:k) - x*I). Can you develop a connection between p_k and its "predecessors" p_{k-1}, p_{k-2}, and p_{k-3}?
Nov 2 Suppose T = lambda*I + N is k-by-k with N strictly upper triangular. This means that T has a single eigenvalue lambda and that it has algebraic multiplicity k. Show that if the dimension of null(T - lambda*I ) = r then there exists an orthogonal V such that V'*T*V = [lambda*eye(r,r) T12; 0 T22] where T12 is r-by(n-r) and T22 is upper triangular and (n-r)-by-(n-r).
Nov 5 Suppose A has all its eigenvalues in the open left half plan. Let f(mu) be the minium singular value of A + mu*i*I.. Show that there is an n-by-n matrix E with norm(E,2) = min f(mu) so that A+E has a purely imaginary eigenvalue.
Nov 7 The Rayleigh quotient r(x) = x'*A*x/x'*x is maximized by setting x to be an eigenvector that corresponds to the most positive eigenvalue. Suppose B is p-by-n with p<n. How could you compute the maximizer of r(x) subject to the constraint that x is in the nullspace of B?
Nov 9 If S is skew-symmetric, then its real Schur decomposition has the form Q'*A*Q = diag(D11,...,Dpp) where each Dii is either 1-by-1 or 2-by-2. Given that this is available, how would you compute M = (I + S)-1(I-S)?
Nov 12 Suppose A's eigenvalues satisfy |lambda_1| = |lambda_2| > lambda_3| >= ...>= |lambda_n| and that it has a full basis of eigenvectors. Is it possible to deduce lambda_1 and lambda_2 from the vectors produced by the power method?
Nov 14 Suppose A is row diagonally dominant with positive diagonal and negative off-diagonal entries. Show that if Ax = b and b>0, then x>0.
Nov 16 Is there a Sturm sequence property for tridiagonal skew-symmetric matrices?
Nov 19 How could the power method be used to find the second largest eigenvalue of a stochastic matrix assuming that the second eigenvalue is real and distinct?
Nov 21 Suppose A is symmetric and has a repeated eigenvalue. Show that the Krylov matrix K(A,q,r) = [q Aq An-1q] is singular.
Nov 26 Suppose after k steps of the Lanczos process we have AQk = Qk*Tk + r*ekT and that r is an eigenvector of A. Does anything special happen during the next step?
Nov 28 Suppose we have solved Ax = b where A is obtained by discretizing the Laplace operator the familiar L-shaped region. Explain why norm(x,inf)<=norm(b,inf)
Nov 30 Suppose A is n-by-n, symmetric, and positive definite. How would you compute Q (n-by-r) with Q'*Q = I so that trace(A*Q*Q') is maximal?