TD_Solution_With_Code
ipynb36 kBPython · 20 cellsSolution of TD 2
Exercise 1- Determinant, EigenValues, EigenVectors and Diagonalization
Consider the matrix:
- Compute the determinant of and verify if it is invertible.
- Find all eigenvalues of by solving the characteristic polynomial.
- For each eigenvalue, determine a corresponding eigenvector.
- Check whether A is diagonalizable, and if yes, find matrices and such that .
Solution
-
To compute the determinant of , we use the formula for the determinant of a 3x3 matrix:
where the matrix elements are:
Plugging in the values from matrix :
Calculating step by step:
- First term:
- Second term:
- Third term:
Since , matrix is invertible.
-
To find the eigenvalues, we solve the characteristic polynomial given by: where is the identity matrix and is the eigenvalue. Thus:
Computing the determinant:
Expanding the first bracket:
Expanding the second bracket:
Expanding the third bracket:
Combining all terms and simplifying yields the characteristic polynomial:
Or equivalently:
We can factor this as:
Therefore, the eigenvalues are:
-
For each eigenvalue, we find the corresponding eigenvector by solving using Gauss-Jordan elimination:
For :
We need to solve:
Apply row reduction to the augmented matrix:
Starting matrix:
:
and :
:
:
:
From the reduced form:
- is free
Choosing , we get:
For :
We need to solve:
Apply row reduction:
Starting matrix:
:
and :
:
:
From the reduced form:
- is free
Choosing , we get:
For :
We need to solve:
Apply row reduction:
Starting matrix:
:
and :
:
:
:
From the reduced form:
- is free
Choosing , we get:
-
Diagonalizability Check:
A matrix is diagonalizable if it has linearly independent eigenvectors, where is the dimension.
We have found three eigenvectors:
To check linear independence, we form the matrix with these vectors as columns and check its determinant:
Since , the eigenvectors are linearly independent, and A is diagonalizable.
The diagonal matrix contains the eigenvalues:
And the decomposition is:
where:
import numpy as np
# Define matrix A
A = np.array([[3 / 2, 1 / 2, -1 / 2], [-1 / 2, 5 / 2, 1 / 2], [-1, 1, 2]])
print("Matrix A:")
print(A)# 1. Compute the determinant
det_A = np.linalg.det(A)
print(f"Determinant of A: {det_A:.4f}")
print(f"Is A invertible? {det_A != 0}")
print(f"Since det(A) ≠ 0, matrix A is invertible.")# 2. Find eigenvalues
eigenvalues, eigenvectors = np.linalg.eig(A)
print("Eigenvalues of A:")
for i, eigenvalue in enumerate(eigenvalues):
print(f" λ{i+1} = {eigenvalue:.6f}")# 3. Find eigenvectors for each eigenvalue
print("\nEigenvectors of A:")
print("Matrix P (columns are eigenvectors):")
print(eigenvectors)
print("\nEach column corresponds to an eigenvalue:")
for i in range(len(eigenvalues)):
print(f"\nEigenvector for λ{i+1} = {eigenvalues[i]:.6f}:")
print(eigenvectors[:, i])# 4. Check if A is diagonalizable
# A matrix is diagonalizable if it has n linearly independent eigenvectors
# where n is the dimension of the matrix
# Check if eigenvectors are linearly independent by checking rank of P
P = eigenvectors
rank_P = np.linalg.matrix_rank(P)
print(f"Rank of eigenvector matrix P: {rank_P}")
print(f"Dimension of A: {A.shape[0]}")
if rank_P == A.shape[0]:
print(
"\nMatrix A is DIAGONALIZABLE because it has 3 linearly independent eigenvectors."
)
else:
print("\nMatrix A is NOT diagonalizable.")# Construct diagonal matrix D with eigenvalues on the diagonal
D = np.diag(eigenvalues)
print("\nMatrix D (diagonal matrix of eigenvalues):")
print(D)
print("\nMatrix P (eigenvectors as columns):")
print(P)# Verify that A = P * D * P^(-1)
P_inv = np.linalg.inv(P)
A_reconstructed = P @ D @ P_inv
print("\nVerification: A = P * D * P^(-1)")
print("\nOriginal matrix A:")
print(A)
print("\nReconstructed A from P * D * P^(-1):")
print(A_reconstructed)
print("\nDifference (should be close to zero):")
print(np.abs(A - A_reconstructed))
print(f"\nMaximum difference: {np.max(np.abs(A - A_reconstructed)):.2e}")
if np.allclose(A, A_reconstructed):
print("\n✓ Verification successful! A = P D P^(-1)")Exercise 2 - Singular Value Decomposition (SVD)
Consider the matrix:
- Show that has a single eigenvalue with only one independent eigenvector. Conclude that is not diagonalizable.
- Compute and its eigenvalues ; set the singular values .
- Find the right singular vectors as eigenvectors of and the left singular vectors .
- Conclude the SVD with , and .
Solution
Part 1: Eigenvalues and Diagonalizability
To find the eigenvalues, we solve the characteristic equation:
Therefore, is the only eigenvalue with algebraic multiplicity 2.
Now, find the eigenvectors by solving :
Apply row reduction:
From this: and is free.
Choosing , we get:
Conclusion: There is only one independent eigenvector for eigenvalue . The geometric multiplicity (1) is less than the algebraic multiplicity (2), so is NOT diagonalizable.
Part 2: Compute and Singular Values
First, compute :
Now compute :
Find eigenvalues of by solving :
Using the quadratic formula:
Therefore:
The singular values are:
Part 3: Right and Left Singular Vectors
Right singular vectors are eigenvectors of .
For :
Solve :
From the first row:
Normalizing with :
After normalization:
For :
Similarly, solving gives:
After normalization:
Left singular vectors are computed as :
Part 4: SVD Decomposition
The Singular Value Decomposition is:
where:
- is a orthogonal matrix of left singular vectors
- is a orthogonal matrix of right singular vectors
This decomposition always exists even when is not diagonalizable, making SVD more general than eigendecomposition.
# Define matrix S
S = np.array([[1, 1], [0, 1]])
print("Matrix S:")
print(S)# Part 1: Find eigenvalues and eigenvectors of S
eigenvalues_S, eigenvectors_S = np.linalg.eig(S)
print("Part 1: Eigenvalues and Eigenvectors of S")
print("=" * 50)
print(f"\nEigenvalues of S: {eigenvalues_S}")
print(f"\nEigenvectors of S:")
print(eigenvectors_S)
# Check rank of eigenvector matrix
rank_eig = np.linalg.matrix_rank(eigenvectors_S)
print(f"\nRank of eigenvector matrix: {rank_eig}")
print(f"Dimension of S: {S.shape[0]}")
if rank_eig < S.shape[0]:
print("\n✗ S is NOT diagonalizable (rank < dimension)")
else:
print("\n✓ S is diagonalizable")# Part 2: Compute S^T S and its eigenvalues, then singular values
S_T = S.T
S_T_S = S_T @ S
print("\nPart 2: S^T S and Singular Values")
print("=" * 50)
print("\nS^T (transpose of S):")
print(S_T)
print("\nS^T S:")
print(S_T_S)
# Find eigenvalues of S^T S
eigenvalues_STS, eigenvectors_STS = np.linalg.eig(S_T_S)
# Sort eigenvalues in descending order
idx = eigenvalues_STS.argsort()[::-1]
eigenvalues_STS = eigenvalues_STS[idx]
eigenvectors_STS = eigenvectors_STS[:, idx]
print(f"\nEigenvalues of S^T S:")
print(f" λ1 = {eigenvalues_STS[0]:.6f}")
print(f" λ2 = {eigenvalues_STS[1]:.6f}")
# Compute singular values
singular_values = np.sqrt(eigenvalues_STS)
print(f"\nSingular values:")
print(f" σ1 = √λ1 = {singular_values[0]:.6f}")
print(f" σ2 = √λ2 = {singular_values[1]:.6f}")# Part 3: Compute right and left singular vectors
print("\nPart 3: Right and Left Singular Vectors")
print("=" * 50)
# Right singular vectors V (eigenvectors of S^T S)
V = eigenvectors_STS
print("\nRight singular vectors V (columns are v1, v2):")
print(V)
print(f"\nv1 = {V[:, 0]}")
print(f"v2 = {V[:, 1]}")
# Left singular vectors U: u_i = S*v_i / σ_i
U = np.zeros((2, 2))
for i in range(2):
U[:, i] = (S @ V[:, i]) / singular_values[i]
print("\nLeft singular vectors U (columns are u1, u2):")
print(U)
print(f"\nu1 = {U[:, 0]}")
print(f"u2 = {U[:, 1]}")
# Verify orthonormality
print("\nVerification of orthonormality:")
print(f"U^T U = \n{U.T @ U}")
print(f"V^T V = \n{V.T @ V}")# Part 4: Construct and verify SVD
print("\nPart 4: Singular Value Decomposition (SVD)")
print("=" * 50)
# Construct diagonal matrix Σ
Sigma = np.diag(singular_values)
print("\nMatrix Σ (diagonal matrix of singular values):")
print(Sigma)
print("\nMatrix U (left singular vectors):")
print(U)
print("\nMatrix V (right singular vectors):")
print(V)
# Reconstruct S using SVD: S = U Σ V^T
S_reconstructed = U @ Sigma @ V.T
print("\n\nVerification: S = U Σ V^T")
print("\nOriginal matrix S:")
print(S)
print("\nReconstructed S from U Σ V^T:")
print(S_reconstructed)
print("\nDifference (should be close to zero):")
print(np.abs(S - S_reconstructed))
print(f"\nMaximum difference: {np.max(np.abs(S - S_reconstructed)):.2e}")
if np.allclose(S, S_reconstructed):
print("\n✓ SVD verification successful! S = U Σ V^T")# Bonus: Compare with NumPy's built-in SVD
print("\n" + "=" * 50)
print("Bonus: Comparison with NumPy's SVD function")
print("=" * 50)
U_numpy, Sigma_numpy, VT_numpy = np.linalg.svd(S)
print("\nNumPy's U:")
print(U_numpy)
print("\nNumPy's singular values:")
print(Sigma_numpy)
print("\nNumPy's V^T:")
print(VT_numpy)
print("\nNumPy's V:")
print(VT_numpy.T)
print("\n\nComparison:")
print(f"Our σ1 = {singular_values[0]:.6f}, NumPy's σ1 = {Sigma_numpy[0]:.6f}")
print(f"Our σ2 = {singular_values[1]:.6f}, NumPy's σ2 = {Sigma_numpy[1]:.6f}")
print("\n✓ Results match (note: signs of vectors may differ, which is normal)")Exercise 3- PCA on a tiny 2D dataset
Given the four points (rows are samples):
- Center the data: compute the column mean and .
- Compute the sample covariance matrix .
- Compute the eigenvalues and eigenvectors of (principal components).
- Order components by decreasing eigenvalues, and give the explained variance ratio for and .
- Project the centered data on the first principal component .
Solution
- Centering the data
- Column mean:
- Centered matrix :
- Sample covariance matrix
- Compute :
- With , the unbiased sample covariance is:
- Eigen-decomposition of
- For a matrix of the form , eigenvalues are with eigenvectors proportional to and .
- Here , :
- Unit-norm eigenvectors:
- Explained variance ratio
- Total variance .
- For (first PC only):
- For (both PCs): EVR .
- Projection onto the first principal component
- Using , the scores are:
Therefore, the principal directions are along and , with the first PC explaining 80% of the variance, and the projections alternate across the four centered points.
# Exercise 3 - PCA (code verification)
import numpy as np
# Data matrix X (4x2)
X = np.array([[2, 0], [0, 2], [3, 1], [1, 3]], dtype=float)
print("X:\n", X)
# 1) Center the data
mu = X.mean(axis=0)
Z = X - mu
print("\nMean mu:", mu)
print("\nCentered Z:\n", Z)
# 2) Sample covariance matrix (unbiased)
C = (Z.T @ Z) / (len(X) - 1)
print("\nCovariance C = (1/(n-1)) Z^T Z:\n", C)
# 3) Eigen-decomposition (symmetric)
vals, vecs = np.linalg.eigh(C) # eigh for symmetric matrices
# Sort in descending order
idx = np.argsort(vals)[::-1]
vals = vals[idx]
vecs = vecs[:, idx]
print("\nEigenvalues (desc):", vals)
print("Eigenvectors (columns, aligned with eigenvalues):\n", vecs)
# 4) Explained variance ratios
explained = vals / vals.sum()
print("\nExplained variance ratios:", explained)
print(f"EVR k=1: {explained[0]:.4f}, EVR k=2: {explained.sum():.4f}")
# 5) Projection on first principal component
v1 = vecs[:, 0]
T1 = Z @ v1
print("\nFirst principal direction v1:", v1)
print("Projection T1 = Z v1:\n", T1)# Bonus: Compare with scikit-learn PCA (optional)
from sklearn.decomposition import PCA
pca = PCA(n_components=2, svd_solver="full")
Z_sklearn = X - X.mean(axis=0)
pca.fit(Z_sklearn)
print("\n[sklearn] Components (rows):\n", pca.components_)
print("[sklearn] Explained variance:", pca.explained_variance_)
print("[sklearn] Explained variance ratio:", pca.explained_variance_ratio_)
# Ensure direction consistency (signs may differ)
print("\nDirection alignment check (abs dot with our v1, v2):")
print("|v1·comp1|:", abs(vecs[:, 0] @ pca.components_[0]))
print("|v2·comp2|:", abs(vecs[:, 1] @ pca.components_[1]))