7.4 Symmetry and definiteness

Key theory:

• spectral decomposition for hermitian (symmetric) matrix: A = VDV$^{-1}$
• hermitian matrices are normal with condition number 1
• SVD of hermitian matrices: : A = (VT)|D|V$^{*}$
• Rayleigh quotient for quadratics shows a good estimate of eigenvector is even better estimate of eigenvalue
• hermitian positive definite: all quadratics are greater than 0 (all eigenvalues are positive)

Exercise 7.4.1

Thanks to spectral decomposition, the eigenvalue problem for hermitian matrices is easier than for general matrices.

1. Let A be a $1000 \times 1000$ random real matrix, and S = A + A$^T$. Time the eigvals function for A and then for S.

A = randn(1000,1000);
S = A + A';

@elapsed eigvals(A)
@elapsed eigvals(S)

2. Perform the experiment from part (a) on $n \times n$ matrices for $n = 200, 300, ..., 1600$. Plot running time as a function of $n$ for both matrices on a single log-log plot. Is the ratio of running times roughly constant, or does it grow with $n$?

n = 200:100:1600;
times_a = [];
times_s = [];

for n in n
  A = randn(n,n);
  S = A + A';
  push!(times_a, @elapsed eigvals(A));
  push!(times_s, @elapsed eigvals(S));
end

scatter(times_a, times_s, xaxis=(:log10, "A times"),
  yaxis=(:log10, "S times"))