Problem Statement

Implement PCA using explicit eigendecomposition of the covariance matrix. Return eigenvalues (descending), explained variance ratios, and the 2D projection.

Algorithm:

1. Center the data: X_c = X - mean(X, axis=0)
2. Compute the unbiased covariance matrix: C = X_cᵀ X_c / (n-1)
3. Compute eigenvalues and eigenvectors using numpy.linalg.eigh (symmetric matrix)
4. Sort eigenvalues in descending order
5. Sign convention: flip each eigenvector so its largest-magnitude component is positive
6. Explained variance ratios: |λ_i| / Σ |λ_j|
7. Project data onto the top 2 eigenvectors: proj2d = X_c @ V[:, :2]

Function signature:

def pca_eigen(X: np.ndarray) -> tuple:
    # returns (eigvals, ratios, proj2d)
    # eigvals: shape (d,) descending, ratios: shape (d,), proj2d: shape (n, 2)

Input Format

Line 1: n d — number of points and dimensions
Lines 2..n+1: d space-separated floats per row

Output Format

Line 1: d eigenvalues (6 decimal places, descending)
Line 2: d explained variance ratios (6 decimal places)
Lines 3..n+2: n rows of the 2D projection (6 decimal places)

Example

Input:

4 3
1.0 2.0 3.0
4.0 5.0 6.0
7.0 8.0 9.0
10.0 11.0 12.0

Output:

45.000000 0.000000 -0.000000
1.000000 0.000000 0.000000
-7.794229 -0.000000
-2.598076 -0.000000
2.598076 0.000000
7.794229 0.000000

Derivation

PCA finds directions of maximum variance. The covariance matrix C is symmetric, so its eigenvectors form an orthonormal basis. The eigenvector with the largest eigenvalue points in the direction of greatest variance. Projecting onto the top k eigenvectors gives the best k-dimensional linear approximation (minimizes reconstruction error by the Eckart-Young theorem).

Notes

• Use numpy.linalg.eigh (not eig) — it exploits symmetry and returns real eigenvalues.
• eigh returns eigenvalues in ascending order; reverse to get descending.
• For data lying on a lower-dimensional subspace (e.g., collinear points), some eigenvalues will be 0 or near-0.