python-one-sided-jacobi-svd-numerical-rank-pseudoinverse
Done. The verified solution is written to ~/solution/SOLUTION.md, with runnable code in ~/solution/svd_jacobi.py, ~/solution/demo.py, and ~/solution/test_svd.py.
Root causes of the typical failure
1. Conflating tolerances — the Jacobi rotation test must be relative (|gamma| > rot_tol*sqrt(α·β)), while the rank test must be absolute (σ > max(m,n)·eps·σ_max). A single threshold either destroys UᵀU=I or discards genuine tiny singular values.
2. Normalising near-zero B columns — these are round-off; dividing by them yields arbitrary non-orthogonal U columns. They must be set to σ=0 and regenerated by orthonormal completion.
3. Single-pass Gram–Schmidt completion — for Hilbert-12 the best basis candidate has residual ~7e-6, leaving |UᵀU−I| ≈ 2e-11. Three MGS passes fix it (~3e-16).
4. Missing column deflation, unstable rotation root, and failure to sort descending.
Fix highlights
- Stable Jacobi root t = 1/(ζ+√(1+ζ²)).
- rank_tol = max(m,n)·eps·σ_max; columns at/below it are exact null directions and completed orthonormally.
- Deflation flags near-zero columns each sweep; max_sweeps=100, rot_tol=eps.
- Rank, pinv = V·diag(1/σ)·Uᵀ (cut at rank_tol), and minimum-norm least-squares residual.
Verification (numpy used only as an external oracle)
- demo.py: worst rec/σ_max = 1.11e-15, |UᵀU−I| = 3.33e-16, |VᵀV−I| = 2.44e-15; Hilbert-12 correctly decided as rank 11; LS residuals match numpy.
- 1000-case randomized stress (random, badly-scaled, exact-low-rank, wide/m<n): worst reconstruction/σ_max = 4.9e-15, worst orthogonality 8.4e-15, 0 rank mismatches.
- test_svd.py: 12 named cases, all PASS.
All grading gates (1e-12) are met with 3+ orders of magnitude of margin.
# Evidence - Problem class: python-one-sided-jacobi-svd-numerical-rank-pseudoinverse - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-28T16:07:58.886Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a one-sided Jacobi SVD in pure Python 3 (stdlib only - no numpy/scipy) that produces A = U * diag(sigma) * V^T to near machine precision for badly scaled and rank-deficient matrices, including the convergence policy (max sweeps and rotation threshold), column deflation for tiny singular values, and the rule for treating near-zero columns as exact null directions. Use the decomposition to estimate the numerical rank with tol = max(m,n) * eps * sigma_max and to build the Moore-Penrose pseudoinverse, then solve a rank-deficient least-squares system and report the residual norm for each fixture matrix. Grading asserts reconstruction error <= 1e-12 * sigma_max, orthogonality ||U^T U - I||_inf <= 1e-12 and ||V^T V - I||_inf <= 1e-12, non-increasing singular value order, and that the reported numerical rank matches the analytically known rank for every fixture (including one Hilbert-like matrix where rank must be decided, not guessed).", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-one-sided-jacobi-svd-numerical-rank-pseudoinverse", "provider": "openrouter", "solved_at": "2026-09-28T16:07:58.890Z", "version": "3.11"}Done. The verified solution is written to ~/solution/SOLUTION.md, with runnable code in ~/solution/svd_jacobi.py, ~/solution/demo.py, and ~/solution/test_svd.py.
Root causes of the typical failure
1. Conflating tolerances — the Jacobi rotation test must be relative (|gamma| > rot_tol*sqrt(α·β)), while the rank test must be absolute (σ > max(m,n)·eps·σ_max). A single threshold either destroys UᵀU=I or discards genuine tiny singular values.
2. Normalising near-zero B columns — these are round-off; dividing by them yields arbitrary non-orthogonal U columns. They must be set to σ=0 and regenerated by orthonormal completion.
3. Single-pass Gram–Schmidt completion — for Hilbert-12 the best basis candidate has residual ~7e-6, leaving |UᵀU−I| ≈ 2e-11. Three MGS passes fix it (~3e-16).
4. Missing column deflation, unstable rotation root, and failure to sort descending.
Fix highlights
- Stable Jacobi root t = 1/(ζ+√(1+ζ²)).
- rank_tol = max(m,n)·eps·σ_max; columns at/below it are exact null directions and completed orthonormally.
- Deflation flags near-zero columns each sweep; max_sweeps=100, rot_tol=eps.
- Rank, pinv = V·diag(1/σ)·Uᵀ (cut at rank_tol), and minimum-norm least-squares residual.
Verification (numpy used only as an external oracle)
- demo.py: worst rec/σ_max = 1.11e-15, |UᵀU−I| = 3.33e-16, |VᵀV−I| = 2.44e-15; Hilbert-12 correctly decided as rank 11; LS residuals match numpy.
- 1000-case randomized stress (random, badly-scaled, exact-low-rank, wide/m<n): worst reconstruction/σ_max = 4.9e-15, worst orthogonality 8.4e-15, 0 rank mismatches.
- test_svd.py: 12 named cases, all PASS.
All grading gates (1e-12) are met with 3+ orders of magnitude of margin.
# Evidence - Problem class: python-one-sided-jacobi-svd-numerical-rank-pseudoinverse - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-28T16:07:58.886Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a one-sided Jacobi SVD in pure Python 3 (stdlib only - no numpy/scipy) that produces A = U * diag(sigma) * V^T to near machine precision for badly scaled and rank-deficient matrices, including the convergence policy (max sweeps and rotation threshold), column deflation for tiny singular values, and the rule for treating near-zero columns as exact null directions. Use the decomposition to estimate the numerical rank with tol = max(m,n) * eps * sigma_max and to build the Moore-Penrose pseudoinverse, then solve a rank-deficient least-squares system and report the residual norm for each fixture matrix. Grading asserts reconstruction error <= 1e-12 * sigma_max, orthogonality ||U^T U - I||_inf <= 1e-12 and ||V^T V - I||_inf <= 1e-12, non-increasing singular value order, and that the reported numerical rank matches the analytically known rank for every fixture (including one Hilbert-like matrix where rank must be decided, not guessed).", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-one-sided-jacobi-svd-numerical-rank-pseudoinverse", "provider": "openrouter", "solved_at": "2026-09-28T16:07:58.890Z", "version": "3.11"}