3. Vectors and Matrices: Exercise Solutions#
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
1) Determinant and eigenvalues#
For a 2x2 matrix \(A = \left(\begin{array}{cc} a & b\\ c & d \end{array}\right)\), let us verify that \(\det A = ad - bc\) in the case graphically shown below (\(a, b, c, d\) are positive).
A = np.array([[4, 1], [2, 3]])
plt.plot([0, 1, 1, 0, 0], [0, 0, 1, 1, 0])
plt.plot([0, A[0,0]+A[0,1], A[0,0]+A[0,1], 0, 0],
[0, 0, A[1,0]+A[1,1], A[1,0]+A[1,1], 0])
plt.plot([A[0,0], A[0,0]+A[0,1], A[0,0]+A[0,1], A[0,0], A[0,0]],
[0, 0, A[1,0], A[1,0], 0])
plt.plot([0, A[0,1], A[0,1], 0, 0],
[A[1,1], A[1,1], A[1,0]+A[1,1], A[1,0]+A[1,1], A[1,1]])
plt.plot([0, A[0,0], A[0,0]+A[0,1], A[0,1], 0],
[0, A[1,0], A[1,0]+A[1,1], A[1,1], 0])
plt.axis('equal')
plt.text(A[0,0], A[1,0], '(a,c)')
plt.text(A[0,1], A[1,1], '(b,d)')
plt.text(A[0,0]+A[0,1], A[1,0]+A[1,1], '(a+b,c+d)');
![_images/ccd79dfa063c31d530538328158a032ea90b42b1bfd07d77dfa3e8003c0d80a9.png](_images/ccd79dfa063c31d530538328158a032ea90b42b1bfd07d77dfa3e8003c0d80a9.png)
A unit square is transformed into a parallelogram. Its area \(S\) can be derived as follows:
Large rectangle: \( S_1 = (a+b)(c+d) = ac+ad+bc+bd \)
Small rectangle: \( S_2 = bc \)
Bottom/top triangle: \( S_3 = ac/2 \)
Left/right triangle: \( S_4 = bd/2 \)
Parallelogram:
$\( S = S_1 - 2S_2 - 2S_3 - 2S_4 = ad - bc\)$
The determinant equals the product of all eigenvalues. Verify this numerically for multiple cases and explain intuitively why that should hold.
#A = np.array([[1, 2], [3, 4]])
m = 4
A = np.random.randn(m,m)
print(A)
lam, V = np.linalg.eig(A)
print('eigenvalues = ', lam)
print('product = ', np.product(lam))
det = np.linalg.det(A)
print('detrminant = ', det)
[[-0.45729474 -0.84126846 0.0910626 -0.01003322]
[-0.67357218 1.09752029 0.52801725 0.18907178]
[-1.5432165 -1.52409312 -0.05344003 -1.13160969]
[ 0.95224655 -0.57217972 -1.23617566 -0.26524343]]
eigenvalues = [-0.8424572 +0.38206847j -0.8424572 -0.38206847j 1.27840878+0.j
0.72804772+0.j ]
product = (0.7964461743563231+1.285678804991634e-17j)
detrminant = 0.7964461743563237
The determinant represents how much the volume in the original space is expanded or shrunk.
The eigenvalues represent how much a segment in the direction of eigen vector is scaled in length.
Therefore, the producs of all eigenvalues should equal to the determinant.
2) Eigenvalues and matrix product#
Make a random (or hand-designed) \(m\times m\) matrix \(A\). Compute its eigenvalues and eigenvectors. From a random (or your preferred) initial point \(\b{x}\), compute \(A\b{x}, A^2\b{x}, A^3\b{x},...\) and visualize the points. Then characterize the behavior of the points with respect the eigenvalues and eigenvectors.
m = 4
A = np.random.randn(m,m)
print('A = ', A)
L, V = np.linalg.eig(A)
print('eigenvalues = ', L)
#print('eigenvectors =\n', V)
A = [[ 0.16566248 0.80769734 0.27644491 -1.69199893]
[ 0.58002476 1.2422395 2.04354629 1.02646402]
[ 1.11832191 -0.55720242 -0.25979387 -0.56499474]
[ 0.16979119 0.05407186 -0.10478714 -0.40297058]]
eigenvalues = [ 1.54646244+0.j -0.48799272+1.04044802j -0.48799272-1.04044802j
0.17466053+0.j ]
# take a point and see how it moves
K = 20 # steps
x = np.zeros((m, K))
x[:,0] = np.random.randn(m) # random initial state
for k in range(K-1):
x[:,k+1] = A @ x[:,k] # x_{k+1} = A x_k
# plot the trajectory
plt.plot( x.T, 'o-')
plt.xlabel("k"); plt.ylabel("$x_i$");
![_images/3115f187472d7e7b6e31d7f696d831b51eb37676da58436871fbd877bfef7ac0.png](_images/3115f187472d7e7b6e31d7f696d831b51eb37676da58436871fbd877bfef7ac0.png)
plt.plot( x[0,:], x[1,:])
[<matplotlib.lines.Line2D at 0x109252e10>]
![_images/88ecf9a7b7d23e22fb9e66b71ac1aa138b5f130e194074e5f3b6e9be48490a06.png](_images/88ecf9a7b7d23e22fb9e66b71ac1aa138b5f130e194074e5f3b6e9be48490a06.png)
Do the above with several different matrices
A = np.random.randn(m,m)
print('A = ', A)
L, V = np.linalg.eig(A)
print('eigenvalues = ', L)
for k in range(K-1):
x[:,k+1] = A @ x[:,k] # x_{k+1} = A x_k
# plot the trajectory
plt.plot( x.T, 'o-')
plt.xlabel("k"); plt.ylabel("$x_i$");
A = [[-0.21389039 -0.04508418 0.91675871 -0.27020227]
[ 0.05762813 0.17563118 -1.18274377 -0.18081118]
[-1.01945225 0.52013657 -1.37120345 -1.14884682]
[-0.23164025 -0.98761936 -0.29326997 -0.36602499]]
eigenvalues = [-1.46764332+0.j -0.26452126+1.04896783j -0.26452126-1.04896783j
0.22119819+0.j ]
![_images/2792132286d394a61e95d6dfc72eba7943720ddc23f6e3befe978ecfe355dbf2.png](_images/2792132286d394a61e95d6dfc72eba7943720ddc23f6e3befe978ecfe355dbf2.png)
3) Principal component analysis#
Read in the “digits” dataset, originally from sklearn
.
data = np.loadtxt("data/digits_data.txt")
target = np.loadtxt("data/digits_target.txt", dtype='int64')
m, n = data.shape
print(m, n)
1797 64
The first ten samples look like these:
plt.figure(figsize=(10,4))
for i in range(10):
plt.subplot(1,10,i+1)
plt.imshow(data[i].reshape((8,8)))
plt.title(target[i])
plt.axis('off')
![_images/e8c25a2be478200705560ddf84b2c5ab9b45ef8ab3e4a510f105a2c66dd54e1d.png](_images/e8c25a2be478200705560ddf84b2c5ab9b45ef8ab3e4a510f105a2c66dd54e1d.png)
Compute the principal component vectors from all the digits and plot the eigenvalues from the largest to smallest.
# subtract the mean
Xm = np.mean(data, axis=0)
X = data - Xm
#C = np.cov(X, rowvar=False)
C = (X.T @ X)/(m-1)
lam, V = np.linalg.eig(C)
# columns of V are eigenvectors
# it is not guaranteed that the eigenvalues are sorted, so sort them
ind = np.argsort(-lam) # indices for sorting, descending order
L = lam[ind]
V = V[:,ind]
print('L, V = ', L, V)
plt.plot(L);
L, V = [1.79006930e+02 1.63717747e+02 1.41788439e+02 1.01100375e+02
6.95131656e+01 5.91085249e+01 5.18845391e+01 4.40151067e+01
4.03109953e+01 3.70117984e+01 2.85190412e+01 2.73211698e+01
2.19014881e+01 2.13243565e+01 1.76367222e+01 1.69468639e+01
1.58513899e+01 1.50044602e+01 1.22344732e+01 1.08868593e+01
1.06935663e+01 9.58259779e+00 9.22640260e+00 8.69036872e+00
8.36561190e+00 7.16577961e+00 6.91973881e+00 6.19295508e+00
5.88499123e+00 5.15586690e+00 4.49129656e+00 4.24687799e+00
4.04743883e+00 3.94340334e+00 3.70647245e+00 3.53165306e+00
3.08457409e+00 2.73780002e+00 2.67210896e+00 2.54170563e+00
2.28298744e+00 1.90724229e+00 1.81716569e+00 1.68996439e+00
1.40197220e+00 1.29221888e+00 1.15893419e+00 9.31220008e-01
6.69850594e-01 4.86065217e-01 2.52350432e-01 9.91527944e-02
6.31307848e-02 6.07377581e-02 3.96662297e-02 1.49505636e-02
8.47307261e-03 3.62365957e-03 1.27705113e-03 6.61270906e-04
4.12223305e-04 0.00000000e+00 0.00000000e+00 0.00000000e+00] [[ 0. 0. 0. ... 1. 0.
0. ]
[ 0.01730947 0.01010646 -0.01834207 ... 0. 0.
0. ]
[ 0.22342883 0.04908492 -0.12647554 ... 0. 0.
0. ]
...
[ 0.08941847 -0.17669712 -0.23208416 ... 0. 0.
0. ]
[ 0.03659771 -0.01945471 -0.16702656 ... 0. 0.
0. ]
[ 0.0114685 0.00669694 -0.03480438 ... 0. 0.
0. ]]
![_images/850f427149a407c45ae7820e3a471c5e2d01c4ce262d789cffffdfee26d2ea1b.png](_images/850f427149a407c45ae7820e3a471c5e2d01c4ce262d789cffffdfee26d2ea1b.png)
# use SVD
U, S, Vt = np.linalg.svd(X, full_matrices=False)
# columns of V, or rows of Vt are eigenvectors
L = S**2/(m-1) # eigenvalues
print('L, Vt = ', L, Vt)
plt.plot(L);
L, Vt = [1.79006930e+02 1.63717747e+02 1.41788439e+02 1.01100375e+02
6.95131656e+01 5.91085249e+01 5.18845391e+01 4.40151067e+01
4.03109953e+01 3.70117984e+01 2.85190412e+01 2.73211698e+01
2.19014881e+01 2.13243565e+01 1.76367222e+01 1.69468639e+01
1.58513899e+01 1.50044602e+01 1.22344732e+01 1.08868593e+01
1.06935663e+01 9.58259779e+00 9.22640260e+00 8.69036872e+00
8.36561190e+00 7.16577961e+00 6.91973881e+00 6.19295508e+00
5.88499123e+00 5.15586690e+00 4.49129656e+00 4.24687799e+00
4.04743883e+00 3.94340334e+00 3.70647245e+00 3.53165306e+00
3.08457409e+00 2.73780002e+00 2.67210896e+00 2.54170563e+00
2.28298744e+00 1.90724229e+00 1.81716569e+00 1.68996439e+00
1.40197220e+00 1.29221888e+00 1.15893419e+00 9.31220008e-01
6.69850594e-01 4.86065217e-01 2.52350432e-01 9.91527944e-02
6.31307848e-02 6.07377581e-02 3.96662297e-02 1.49505636e-02
8.47307261e-03 3.62365957e-03 1.27705113e-03 6.61270906e-04
4.12223305e-04 1.14286697e-30 1.14286697e-30 1.12542605e-30] [[ 1.77484909e-19 1.73094651e-02 2.23428835e-01 ... 8.94184677e-02
3.65977111e-02 1.14684954e-02]
[-3.27805401e-18 1.01064569e-02 4.90849204e-02 ... -1.76697117e-01
-1.94547053e-02 6.69693895e-03]
[ 1.68358559e-18 -1.83420720e-02 -1.26475543e-01 ... -2.32084163e-01
-1.67026563e-01 -3.48043832e-02]
...
[ 0.00000000e+00 5.01431234e-17 -9.75867742e-17 ... -6.93889390e-17
5.55111512e-17 -3.46944695e-18]
[ 0.00000000e+00 4.27173158e-16 -3.24255744e-16 ... 1.11022302e-16
-5.55111512e-17 1.38777878e-16]
[-1.00000000e+00 1.68983002e-17 -5.73338351e-18 ... -8.66631300e-18
1.57615962e-17 -4.07058917e-18]]
![_images/850f427149a407c45ae7820e3a471c5e2d01c4ce262d789cffffdfee26d2ea1b.png](_images/850f427149a407c45ae7820e3a471c5e2d01c4ce262d789cffffdfee26d2ea1b.png)
Visualize the principal vectors as images.
plt.figure(figsize=(8,8))
for i in range(n):
plt.subplot(8,8,i+1)
plt.imshow(V[:,i].reshape((8,8)))
#plt.imshow(Vt[i].reshape((8,8)))
plt.axis('off')
![_images/708352ece4d0302117d37762bda33cf31ee16822b54234e24a1b5ff8f6c8f57e.png](_images/708352ece4d0302117d37762bda33cf31ee16822b54234e24a1b5ff8f6c8f57e.png)
Scatterplot the digits in the first two or three principal component space, with different colors/markers for digits.
# columns of V are eigenvectors
Z = X @ V
plt.scatter(Z[:,0], Z[:,1], c=target, marker='.')
plt.setp(plt.gca(), xlabel='PC1', ylabel='PC2')
plt.axis('square');
![_images/2e7c6614c566b383a75a036105000d596d2a2584c3ce8fd5f5ff93e1b39aa14a.png](_images/2e7c6614c566b383a75a036105000d596d2a2584c3ce8fd5f5ff93e1b39aa14a.png)
plt.figure(figsize=(8,8))
plt.scatter(Z[:,0], Z[:,1], c=target, marker='.')
# add labels to some points
for i in range(100):
plt.text(Z[i,0], Z[i,1], str(target[i]))
plt.setp(plt.gca(), xlabel='PC1', ylabel='PC2');
![_images/886f36b421582e12734ab13866d7294e255ba0f6794bf0a30818b5e147d0898f.png](_images/886f36b421582e12734ab13866d7294e255ba0f6794bf0a30818b5e147d0898f.png)
# In 3D
fig = plt.figure(figsize=(8,8))
ax = fig.add_subplot(projection='3d')
ax.scatter(Z[:,0], Z[:,1], Z[:,2], c=target, marker='o')
# add labels to some points
for i in range(200):
ax.text(Z[i,0], Z[i,1], Z[i,2], str(target[i]))
plt.setp(plt.gca(), xlabel='PC1', ylabel='PC2', zlabel='PC3');
![_images/9cd587d80ab363c83208934bedea474833ae02e255cd1973070eb471d3a84fd1.png](_images/9cd587d80ab363c83208934bedea474833ae02e255cd1973070eb471d3a84fd1.png)
Take a sample digit, decompose it into principal components, and reconstruct the digit from the first \(m\) components. See how the quality of reproduction depends on \(m\).
K = 8 # PCs to be considered
i = np.random.randint(m) # pick a random sample
plt.figure(figsize=(10,4))
plt.subplot(1,K,1)
plt.imshow(data[i].reshape((8,8))) # original
plt.title(target[i])
plt.axis('off')
for k in range(1,K): # number of PCs
Xrec = Xm + V[:,:k] @ Z[i,:k]
plt.subplot(1,K,k+1)
plt.imshow(Xrec.reshape((8,8))) # reconstructed
plt.title(k)
plt.axis('off')
![_images/2a85df70d1711744e0d3636ca4fb85d152ae5ac49721d71fa9fd28a25c19f7f0.png](_images/2a85df70d1711744e0d3636ca4fb85d152ae5ac49721d71fa9fd28a25c19f7f0.png)