TD_Solution_With_Code

ipynb36 kBPython · 20 cellsSolution of TD 2

Exercise 1- Determinant, EigenValues, EigenVectors and Diagonalization

Consider the matrix:

A=(3/21/2−1/2−1/25/21/2−112)A = \begin{pmatrix} 3/2 & 1/2 & -1/2 \\ -1/2 & 5/2 & 1/2 \\ -1 & 1 & 2 \\ \end{pmatrix}
  1. Compute the determinant of AA and verify if it is invertible.
  2. Find all eigenvalues of AA by solving the characteristic polynomial.
  3. For each eigenvalue, determine a corresponding eigenvector.
  4. Check whether A is diagonalizable, and if yes, find matrices PP and DD such that A=PDP−1A = P D P^{-1}.

Solution

  1. To compute the determinant of AA, we use the formula for the determinant of a 3x3 matrix:

    det(A)=a(ei−fh)−b(di−fg)+c(dh−eg)\text{det}(A) = a(ei - fh) - b(di - fg) + c(dh - eg)

    where the matrix elements are:

    A=(abcdefghi)A = \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \\ \end{pmatrix}

    Plugging in the values from matrix AA:

    det(A)=32(52⋅2−12⋅1)−12(−12⋅2−12⋅(−1))+(−12)(−12⋅1−52⋅(−1))\text{det}(A) = \frac{3}{2} \left( \frac{5}{2} \cdot 2 - \frac{1}{2} \cdot 1 \right) - \frac{1}{2} \left( -\frac{1}{2} \cdot 2 - \frac{1}{2} \cdot (-1) \right) + \left( -\frac{1}{2} \right) \left( -\frac{1}{2} \cdot 1 - \frac{5}{2} \cdot (-1) \right)

    Calculating step by step:

    • First term: 32(5−12)=32⋅92=274\frac{3}{2}(5 - \frac{1}{2}) = \frac{3}{2} \cdot \frac{9}{2} = \frac{27}{4}
    • Second term: −12(−1+12)=−12⋅(−12)=14-\frac{1}{2}(-1 + \frac{1}{2}) = -\frac{1}{2} \cdot (-\frac{1}{2}) = \frac{1}{4}
    • Third term: −12(−12+52)=−12⋅2=−1-\frac{1}{2}(-\frac{1}{2} + \frac{5}{2}) = -\frac{1}{2} \cdot 2 = -1
    det(A)=274+14−1=284−1=7−1=6\text{det}(A) = \frac{27}{4} + \frac{1}{4} - 1 = \frac{28}{4} - 1 = 7 - 1 = 6

    Since det(A)=6≠0\text{det}(A) = 6 \neq 0, matrix AA is invertible.

  2. To find the eigenvalues, we solve the characteristic polynomial given by: det(A−λI)=0\text{det}(A - \lambda I) = 0 where II is the identity matrix and λ\lambda is the eigenvalue. Thus:

    A−λI=(32−λ12−12−1252−λ12−112−λ)A - \lambda I = \begin{pmatrix} \frac{3}{2} - \lambda & \frac{1}{2} & -\frac{1}{2} \\ -\frac{1}{2} & \frac{5}{2} - \lambda & \frac{1}{2} \\ -1 & 1 & 2 - \lambda \\ \end{pmatrix}

    Computing the determinant:

    det(A−λI)=(32−λ)[(52−λ)(2−λ)−12⋅1]−12[−12(2−λ)−12⋅(−1)]+(−12)[−12⋅1−(52−λ)(−1)]\text{det}(A - \lambda I) = \left(\frac{3}{2} - \lambda\right) \left[\left(\frac{5}{2} - \lambda\right)(2 - \lambda) - \frac{1}{2} \cdot 1\right] - \frac{1}{2}\left[-\frac{1}{2}(2 - \lambda) - \frac{1}{2} \cdot (-1)\right] + \left(-\frac{1}{2}\right)\left[-\frac{1}{2} \cdot 1 - \left(\frac{5}{2} - \lambda\right)(-1)\right]

    Expanding the first bracket: (52−λ)(2−λ)−12=5−5λ2−2λ+λ2−12=λ2−9λ2+92\left(\frac{5}{2} - \lambda\right)(2 - \lambda) - \frac{1}{2} = 5 - \frac{5\lambda}{2} - 2\lambda + \lambda^2 - \frac{1}{2} = \lambda^2 - \frac{9\lambda}{2} + \frac{9}{2}

    Expanding the second bracket: −12(2−λ)−12(−1)=−1+λ2+12=λ2−12-\frac{1}{2}(2 - \lambda) - \frac{1}{2}(-1) = -1 + \frac{\lambda}{2} + \frac{1}{2} = \frac{\lambda}{2} - \frac{1}{2}

    Expanding the third bracket: −12−(−1)(52−λ)=−12+52−λ=2−λ-\frac{1}{2} - (-1)\left(\frac{5}{2} - \lambda\right) = -\frac{1}{2} + \frac{5}{2} - \lambda = 2 - \lambda

    Combining all terms and simplifying yields the characteristic polynomial: −λ3+6λ2−11λ+6=0-\lambda^3 + 6\lambda^2 - 11\lambda + 6 = 0

    Or equivalently: λ3−6λ2+11λ−6=0\lambda^3 - 6\lambda^2 + 11\lambda - 6 = 0

    We can factor this as: (λ−1)(λ−2)(λ−3)=0(\lambda - 1)(\lambda - 2)(\lambda - 3) = 0

    Therefore, the eigenvalues are:

    • λ1=1\lambda_1 = 1
    • λ2=2\lambda_2 = 2
    • λ3=3\lambda_3 = 3
  3. For each eigenvalue, we find the corresponding eigenvector by solving (A−λI)v⃗=0⃗(A - \lambda I)\vec{v} = \vec{0} using Gauss-Jordan elimination:

    For λ1=1\lambda_1 = 1:

    We need to solve:

    (A−I)v⃗=(1/21/2−1/2−1/23/21/2−111)(v1v2v3)=(000)(A - I)\vec{v} = \begin{pmatrix} 1/2 & 1/2 & -1/2 \\ -1/2 & 3/2 & 1/2 \\ -1 & 1 & 1 \\ \end{pmatrix} \begin{pmatrix} v_1 \\ v_2 \\ v_3 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}

    Apply row reduction to the augmented matrix:

    Starting matrix:

    [1/21/2−1/20−1/23/21/20−1110]\left[\begin{array}{ccc|c} 1/2 & 1/2 & -1/2 & 0 \\ -1/2 & 3/2 & 1/2 & 0 \\ -1 & 1 & 1 & 0 \end{array}\right]

    R1×2R_1 \times 2:

    [11−10−1/23/21/20−1110]\left[\begin{array}{ccc|c} 1 & 1 & -1 & 0 \\ -1/2 & 3/2 & 1/2 & 0 \\ -1 & 1 & 1 & 0 \end{array}\right]

    R2+12R1R_2 + \frac{1}{2}R_1 and R3+R1R_3 + R_1:

    [11−1002000200]\left[\begin{array}{ccc|c} 1 & 1 & -1 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 2 & 0 & 0 \end{array}\right]

    R2×12R_2 \times \frac{1}{2}:

    [11−1001000200]\left[\begin{array}{ccc|c} 1 & 1 & -1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 2 & 0 & 0 \end{array}\right]

    R3−2R2R_3 - 2R_2:

    [11−1001000000]\left[\begin{array}{ccc|c} 1 & 1 & -1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array}\right]

    R1−R2R_1 - R_2:

    [10−1001000000]\left[\begin{array}{ccc|c} 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array}\right]

    From the reduced form:

    • v1−v3=0⇒v1=v3v_1 - v_3 = 0 \Rightarrow v_1 = v_3
    • v2=0v_2 = 0
    • v3v_3 is free

    Choosing v3=1v_3 = 1, we get: v⃗1=(101)\vec{v}_1 = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}

    For λ2=2\lambda_2 = 2:

    We need to solve:

    (A−2I)v⃗=(−1/21/2−1/2−1/21/21/2−110)(v1v2v3)=(000)(A - 2I)\vec{v} = \begin{pmatrix} -1/2 & 1/2 & -1/2 \\ -1/2 & 1/2 & 1/2 \\ -1 & 1 & 0 \\ \end{pmatrix} \begin{pmatrix} v_1 \\ v_2 \\ v_3 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}

    Apply row reduction:

    Starting matrix:

    [−1/21/2−1/20−1/21/21/20−1100]\left[\begin{array}{ccc|c} -1/2 & 1/2 & -1/2 & 0 \\ -1/2 & 1/2 & 1/2 & 0 \\ -1 & 1 & 0 & 0 \end{array}\right]

    R1×(−2)R_1 \times (-2):

    [1−110−1/21/21/20−1100]\left[\begin{array}{ccc|c} 1 & -1 & 1 & 0 \\ -1/2 & 1/2 & 1/2 & 0 \\ -1 & 1 & 0 & 0 \end{array}\right]

    R2+12R1R_2 + \frac{1}{2}R_1 and R3+R1R_3 + R_1:

    [1−11000100010]\left[\begin{array}{ccc|c} 1 & -1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 \end{array}\right]

    R3−R2R_3 - R_2:

    [1−11000100000]\left[\begin{array}{ccc|c} 1 & -1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{array}\right]

    R1−R2R_1 - R_2:

    [1−10000100000]\left[\begin{array}{ccc|c} 1 & -1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{array}\right]

    From the reduced form:

    • v1−v2=0⇒v1=v2v_1 - v_2 = 0 \Rightarrow v_1 = v_2
    • v3=0v_3 = 0
    • v2v_2 is free

    Choosing v2=1v_2 = 1, we get: v⃗2=(110)\vec{v}_2 = \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix}

    For λ3=3\lambda_3 = 3:

    We need to solve:

    (A−3I)v⃗=(−3/21/2−1/2−1/2−1/21/2−11−1)(v1v2v3)=(000)(A - 3I)\vec{v} = \begin{pmatrix} -3/2 & 1/2 & -1/2 \\ -1/2 & -1/2 & 1/2 \\ -1 & 1 & -1 \\ \end{pmatrix} \begin{pmatrix} v_1 \\ v_2 \\ v_3 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}

    Apply row reduction:

    Starting matrix:

    [−3/21/2−1/20−1/2−1/21/20−11−10]\left[\begin{array}{ccc|c} -3/2 & 1/2 & -1/2 & 0 \\ -1/2 & -1/2 & 1/2 & 0 \\ -1 & 1 & -1 & 0 \end{array}\right]

    R1×(−2/3)R_1 \times (-2/3):

    [1−1/31/30−1/2−1/21/20−11−10]\left[\begin{array}{ccc|c} 1 & -1/3 & 1/3 & 0 \\ -1/2 & -1/2 & 1/2 & 0 \\ -1 & 1 & -1 & 0 \end{array}\right]

    R2+12R1R_2 + \frac{1}{2}R_1 and R3+R1R_3 + R_1:

    [1−1/31/300−2/32/3002/3−2/30]\left[\begin{array}{ccc|c} 1 & -1/3 & 1/3 & 0 \\ 0 & -2/3 & 2/3 & 0 \\ 0 & 2/3 & -2/3 & 0 \end{array}\right]

    R2×(−3/2)R_2 \times (-3/2):

    [1−1/31/3001−1002/3−2/30]\left[\begin{array}{ccc|c} 1 & -1/3 & 1/3 & 0 \\ 0 & 1 & -1 & 0 \\ 0 & 2/3 & -2/3 & 0 \end{array}\right]

    R3−23R2R_3 - \frac{2}{3}R_2:

    [1−1/31/3001−100000]\left[\begin{array}{ccc|c} 1 & -1/3 & 1/3 & 0 \\ 0 & 1 & -1 & 0 \\ 0 & 0 & 0 & 0 \end{array}\right]

    R1+13R2R_1 + \frac{1}{3}R_2:

    [100001−100000]\left[\begin{array}{ccc|c} 1 & 0 & 0 & 0 \\ 0 & 1 & -1 & 0 \\ 0 & 0 & 0 & 0 \end{array}\right]

    From the reduced form:

    • v1=0v_1 = 0
    • v2−v3=0⇒v2=v3v_2 - v_3 = 0 \Rightarrow v_2 = v_3
    • v3v_3 is free

    Choosing v3=1v_3 = 1, we get: v⃗3=(011)\vec{v}_3 = \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix}

  4. Diagonalizability Check:

    A matrix AA is diagonalizable if it has nn linearly independent eigenvectors, where nn is the dimension.

    We have found three eigenvectors:

    v⃗1=(101),v⃗2=(110),v⃗3=(011)\vec{v}_1 = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}, \quad \vec{v}_2 = \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix}, \quad \vec{v}_3 = \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix}

    To check linear independence, we form the matrix with these vectors as columns and check its determinant:

    P=(110011101)P = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ \end{pmatrix} det(P)=1(1⋅1−1⋅0)−1(0⋅1−1⋅1)+0(0⋅0−1⋅1)=1(1)−1(−1)+0=1+1=2≠0\text{det}(P) = 1(1 \cdot 1 - 1 \cdot 0) - 1(0 \cdot 1 - 1 \cdot 1) + 0(0 \cdot 0 - 1 \cdot 1) = 1(1) - 1(-1) + 0 = 1 + 1 = 2 \neq 0

    Since det(P)≠0\text{det}(P) \neq 0, the eigenvectors are linearly independent, and A is diagonalizable.

    The diagonal matrix DD contains the eigenvalues:

    D=(100020003)D = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \\ \end{pmatrix}

    And the decomposition is:

    A=PDP−1A = PDP^{-1}

    where:

    P=(110011101),D=(100020003)P = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ \end{pmatrix}, \quad D = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \\ \end{pmatrix}
In [ ]
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)
In [ ]
# 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.")
In [ ]
# 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}")
In [ ]
# 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])
In [ ]
# 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.")
In [ ]
# 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)
In [ ]
# 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:

S=(1101)S = \begin{pmatrix} 1 & 1 \\ 0 & 1 \\ \end{pmatrix}
  1. Show that SS has a single eigenvalue λ=1\lambda = 1 with only one independent eigenvector. Conclude that SS is not diagonalizable.
  2. Compute STSS^T S and its eigenvalues {λ1,λ2}\{\lambda_1, \lambda_2\}; set the singular values σi=λi\sigma_i = \sqrt{\lambda_i}.
  3. Find the right singular vectors viv_i as eigenvectors of STSS^T S and the left singular vectors ui=Sviσiu_i = \frac{Sv_i}{\sigma_i}.
  4. Conclude the SVD S=UΣVTS = U \Sigma V^T with U=[u1  u2]U = [u_1\; u_2], V=[v1  v2]V = [v_1\; v_2] and Σ=diag⁡(σ1,σ2)\Sigma = \operatorname{diag}(\sigma_1, \sigma_2).

Solution

Part 1: Eigenvalues and Diagonalizability

To find the eigenvalues, we solve the characteristic equation: det(S−λI)=0\text{det}(S - \lambda I) = 0

S−λI=(1−λ101−λ)S - \lambda I = \begin{pmatrix} 1 - \lambda & 1 \\ 0 & 1 - \lambda \\ \end{pmatrix} det(S−λI)=(1−λ)(1−λ)−0⋅1=(1−λ)2=0\text{det}(S - \lambda I) = (1 - \lambda)(1 - \lambda) - 0 \cdot 1 = (1 - \lambda)^2 = 0

Therefore, λ=1\lambda = 1 is the only eigenvalue with algebraic multiplicity 2.

Now, find the eigenvectors by solving (S−I)v⃗=0⃗(S - I)\vec{v} = \vec{0}:

(S−I)=(0100)(S - I) = \begin{pmatrix} 0 & 1 \\ 0 & 0 \\ \end{pmatrix}

Apply row reduction:

[010000]\left[\begin{array}{cc|c} 0 & 1 & 0 \\ 0 & 0 & 0 \end{array}\right]

From this: v2=0v_2 = 0 and v1v_1 is free.

Choosing v1=1v_1 = 1, we get: v⃗=(10)\vec{v} = \begin{pmatrix} 1 \\ 0 \end{pmatrix}

Conclusion: There is only one independent eigenvector for eigenvalue λ=1\lambda = 1. The geometric multiplicity (1) is less than the algebraic multiplicity (2), so SS is NOT diagonalizable.

Part 2: Compute STSS^T S and Singular Values

First, compute STS^T:

ST=(1011)S^T = \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ \end{pmatrix}

Now compute STSS^T S:

STS=(1011)(1101)=(1112)S^T S = \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 1 \\ \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 2 \\ \end{pmatrix}

Find eigenvalues of STSS^T S by solving det(STS−λI)=0\text{det}(S^T S - \lambda I) = 0:

det(1−λ112−λ)=(1−λ)(2−λ)−1=2−λ−2λ+λ2−1=λ2−3λ+1=0\text{det}\begin{pmatrix} 1 - \lambda & 1 \\ 1 & 2 - \lambda \\ \end{pmatrix} = (1 - \lambda)(2 - \lambda) - 1 = 2 - \lambda - 2\lambda + \lambda^2 - 1 = \lambda^2 - 3\lambda + 1 = 0

Using the quadratic formula:

λ=3±9−42=3±52\lambda = \frac{3 \pm \sqrt{9 - 4}}{2} = \frac{3 \pm \sqrt{5}}{2}

Therefore:

  • λ1=3+52≈2.618\lambda_1 = \frac{3 + \sqrt{5}}{2} \approx 2.618
  • λ2=3−52≈0.382\lambda_2 = \frac{3 - \sqrt{5}}{2} \approx 0.382

The singular values are:

σ1=λ1=3+52≈1.618\sigma_1 = \sqrt{\lambda_1} = \sqrt{\frac{3 + \sqrt{5}}{2}} \approx 1.618 σ2=λ2=3−52≈0.618\sigma_2 = \sqrt{\lambda_2} = \sqrt{\frac{3 - \sqrt{5}}{2}} \approx 0.618

Part 3: Right and Left Singular Vectors

Right singular vectors are eigenvectors of STSS^T S.

For λ1=3+52\lambda_1 = \frac{3 + \sqrt{5}}{2}:

Solve (STS−λ1I)v⃗1=0⃗(S^T S - \lambda_1 I)\vec{v}_1 = \vec{0}:

(1−3+52112−3+52)=(−1−52111−52)\begin{pmatrix} 1 - \frac{3 + \sqrt{5}}{2} & 1 \\ 1 & 2 - \frac{3 + \sqrt{5}}{2} \\ \end{pmatrix} = \begin{pmatrix} \frac{-1 - \sqrt{5}}{2} & 1 \\ 1 & \frac{1 - \sqrt{5}}{2} \\ \end{pmatrix}

From the first row: −1−52v1+v2=0\frac{-1 - \sqrt{5}}{2}v_1 + v_2 = 0

v2=1+52v1v_2 = \frac{1 + \sqrt{5}}{2}v_1

Normalizing with v1=1v_1 = 1: v⃗1=(11+52)\vec{v}_1 = \begin{pmatrix} 1 \\ \frac{1 + \sqrt{5}}{2} \end{pmatrix}

After normalization: v⃗1=11+(1+52)2(11+52)\vec{v}_1 = \frac{1}{\sqrt{1 + \left(\frac{1+\sqrt{5}}{2}\right)^2}} \begin{pmatrix} 1 \\ \frac{1 + \sqrt{5}}{2} \end{pmatrix}

For λ2=3−52\lambda_2 = \frac{3 - \sqrt{5}}{2}:

Similarly, solving (STS−λ2I)v⃗2=0⃗(S^T S - \lambda_2 I)\vec{v}_2 = \vec{0} gives:

v2=1−52v1v_2 = \frac{1 - \sqrt{5}}{2}v_1

After normalization: v⃗2=11+(1−52)2(11−52)\vec{v}_2 = \frac{1}{\sqrt{1 + \left(\frac{1-\sqrt{5}}{2}\right)^2}} \begin{pmatrix} 1 \\ \frac{1 - \sqrt{5}}{2} \end{pmatrix}

Left singular vectors are computed as ui=Sviσiu_i = \frac{Sv_i}{\sigma_i}:

u1=Sv1σ1,u2=Sv2σ2u_1 = \frac{Sv_1}{\sigma_1}, \quad u_2 = \frac{Sv_2}{\sigma_2}

Part 4: SVD Decomposition

The Singular Value Decomposition is:

S=UΣVTS = U \Sigma V^T

where:

  • U=[u1  u2]U = [u_1\; u_2] is a 2×22 \times 2 orthogonal matrix of left singular vectors
  • Σ=(σ100σ2)=(3+52003−52)\Sigma = \begin{pmatrix} \sigma_1 & 0 \\ 0 & \sigma_2 \end{pmatrix} = \begin{pmatrix} \sqrt{\frac{3+\sqrt{5}}{2}} & 0 \\ 0 & \sqrt{\frac{3-\sqrt{5}}{2}} \end{pmatrix}
  • V=[v1  v2]V = [v_1\; v_2] is a 2×22 \times 2 orthogonal matrix of right singular vectors

This decomposition always exists even when SS is not diagonalizable, making SVD more general than eigendecomposition.

In [ ]
# Define matrix S
S = np.array([[1, 1], [0, 1]])

print("Matrix S:")
print(S)
In [ ]
# 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")
In [ ]
# 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}")
In [ ]
# 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}")
In [ ]
# 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")
In [ ]
# 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):

X=(20023113)∈R4×2X = \begin{pmatrix} 2 & 0 \\ 0 & 2 \\ 3 & 1 \\ 1 & 3 \\ \end{pmatrix} \in \mathbb{R}^{4 \times 2}
  1. Center the data: compute the column mean μ\mu and Z=X−1 μTZ = X - \mathbf{1}\,\mu^T.
  2. Compute the sample covariance matrix C=1n−1ZTZC = \frac{1}{n-1} Z^T Z.
  3. Compute the eigenvalues and eigenvectors of CC (principal components).
  4. Order components by decreasing eigenvalues, and give the explained variance ratio for k=1k = 1 and k=2k = 2.
  5. Project the centered data on the first principal component T1=Zv1T_1 = Z v_1.

Solution

  1. Centering the data
  • Column mean: μ=14∑i=14Xi,:=(2+0+3+140+2+1+34)=(1.51.5)\mu = \frac{1}{4} \sum_{i=1}^4 X_{i,:} = \begin{pmatrix} \tfrac{2+0+3+1}{4} \\ \tfrac{0+2+1+3}{4} \end{pmatrix} = \begin{pmatrix} 1.5 \\ 1.5 \end{pmatrix}
  • Centered matrix Z=X−1 μTZ = X - \mathbf{1}\,\mu^T: Z=(2−1.50−1.50−1.52−1.53−1.51−1.51−1.53−1.5)=(0.5−1.5−1.50.51.5−0.5−0.51.5)Z = \begin{pmatrix} 2-1.5 & 0-1.5 \\ 0-1.5 & 2-1.5 \\ 3-1.5 & 1-1.5 \\ 1-1.5 & 3-1.5 \\ \end{pmatrix} = \begin{pmatrix} 0.5 & -1.5 \\ -1.5 & 0.5 \\ 1.5 & -0.5 \\ -0.5 & 1.5 \\ \end{pmatrix}
  1. Sample covariance matrix
  • Compute ZTZZ^T Z: ZTZ=(5−3−35)Z^T Z = \begin{pmatrix} 5 & -3 \\ -3 & 5 \\ \end{pmatrix}
  • With n=4n=4, the unbiased sample covariance is: C=1n−1ZTZ=13(5−3−35)=(53−1−153)C = \frac{1}{n-1} Z^T Z = \frac{1}{3} \begin{pmatrix} 5 & -3 \\ -3 & 5 \end{pmatrix} = \begin{pmatrix} \tfrac{5}{3} & -1 \\ -1 & \tfrac{5}{3} \end{pmatrix}
  1. Eigen-decomposition of CC
  • For a matrix of the form (abba)\begin{pmatrix} a & b \\ b & a \end{pmatrix}, eigenvalues are a±ba\pm b with eigenvectors proportional to (11)\begin{pmatrix} 1 \\ 1 \end{pmatrix} and (1−1)\begin{pmatrix} 1 \\ -1 \end{pmatrix}.
  • Here a=53a=\tfrac{5}{3}, b=−1b=-1: λ1=a−b=53−(−1)=83≈2.6667,v1∝(1−1)\lambda_1 = a - b = \tfrac{5}{3} - (-1) = \tfrac{8}{3} \approx 2.6667, \quad v_1 \propto \begin{pmatrix} 1 \\ -1 \end{pmatrix} λ2=a+b=53+(−1)=23≈0.6667,v2∝(11)\lambda_2 = a + b = \tfrac{5}{3} + (-1) = \tfrac{2}{3} \approx 0.6667, \quad v_2 \propto \begin{pmatrix} 1 \\ 1 \end{pmatrix}
  • Unit-norm eigenvectors: v1=12(1−1),v2=12(11)v_1 = \tfrac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ -1 \end{pmatrix},\quad v_2 = \tfrac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ 1 \end{pmatrix}
  1. Explained variance ratio
  • Total variance =λ1+λ2=83+23=103= \lambda_1 + \lambda_2 = \tfrac{8}{3} + \tfrac{2}{3} = \tfrac{10}{3}.
  • For k=1k=1 (first PC only): EVRk=1=λ1λ1+λ2=83103=810=0.8\text{EVR}_{k=1} = \frac{\lambda_1}{\lambda_1+\lambda_2} = \frac{\tfrac{8}{3}}{\tfrac{10}{3}} = \frac{8}{10} = 0.8
  • For k=2k=2 (both PCs): EVR =1.0=1.0.
  1. Projection onto the first principal component
  • Using v1=12(1,−1)Tv_1 = \tfrac{1}{\sqrt{2}}(1, -1)^T, the scores T1=Zv1T_1 = Z v_1 are: T1=12(0.5−(−1.5)−1.5−0.51.5−(−0.5)−0.5−1.5)=12(2−22−2)=(2−22−2)T_1 = \frac{1}{\sqrt{2}} \begin{pmatrix} 0.5 - (-1.5) \\ -1.5 - 0.5 \\ 1.5 - (-0.5) \\ -0.5 - 1.5 \\ \end{pmatrix} = \frac{1}{\sqrt{2}} \begin{pmatrix} 2 \\ -2 \\ 2 \\ -2 \\ \end{pmatrix} = \begin{pmatrix} \sqrt{2} \\ -\sqrt{2} \\ \sqrt{2} \\ -\sqrt{2} \\ \end{pmatrix}

Therefore, the principal directions are along (1,−1)(1,-1) and (1,1)(1,1), with the first PC explaining 80% of the variance, and the projections alternate ±2\pm\sqrt{2} across the four centered points.

In [ ]
# 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)
In [ ]
# 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]))

In TD 2