TheAlgorithms/Java · error · ArithmeticException

Matrix is rank deficient. Cannot perform QR decomposition.

Error message

Matrix is rank deficient. Cannot perform QR decomposition.

What it means

Thrown by QRDecomposition.decompose (as an ArithmeticException, not IllegalArgumentException) when the Gram-Schmidt process computes a zero norm for the residual of a column (r[j][j] == 0). A zero residual means that column is linearly dependent on the already-orthonormalized earlier columns, so the matrix is rank-deficient and no valid orthogonal Q exists; dividing by r[j][j] would also divide by zero.

Source

Thrown at src/main/java/com/thealgorithms/matrix/QRDecomposition.java:64

        int m = matrix.length;
        int n = matrix[0].length;

        double[][] q = new double[m][n];
        double[][] r = new double[n][n];

        for (int j = 0; j < n; j++) {
            double[] v = getColumn(matrix, j);

            for (int i = 0; i < j; i++) {
                double[] qi = getColumn(q, i);
                r[i][j] = dotProduct(qi, v);
                v = subtractVectors(v, scalarMultiply(qi, r[i][j]));
            }

            r[j][j] = norm(v);
            if (r[j][j] == 0) {
                throw new ArithmeticException("Matrix is rank deficient. Cannot perform QR decomposition.");
            }
            double[] qj = scalarMultiply(v, 1.0 / r[j][j]);
            setColumn(q, j, qj);
        }

        return new QR(q, r);
    }

    private static double[] getColumn(double[][] matrix, int col) {
        int m = matrix.length;
        double[] column = new double[m];
        for (int i = 0; i < m; i++) {
            column[i] = matrix[i][col];
        }
        return column;
    }

    private static void setColumn(double[][] matrix, int col, double[] column) {

View on GitHub (pinned to fdfb9a395b)

Solutions

1. Pre-check rank (e.g., via SVD or by computing column independence) and drop/recombine dependent columns before decompose.
2. Switch to a rank-revealing QR (column pivoting) or SVD-based decomposition that tolerates rank deficiency.
3. Add tiny regularization or perturbation if near-deficiency is causing exact-zero residuals in float data.

Example fix

// before
QRDecomposition.QR qr = QRDecomposition.depose(matrix); // typo aside

// after
// remove linearly dependent columns first (e.g., via a rank check)
double[][] fullRank = removeDependentColumns(matrix);
QRDecomposition.QR qr = QRDecomposition.decompose(fullRank);

// approximate rank check via independent columns
boolean fullRank = hasIndependentColumns(matrix); // your rank-revealing helper
if (!fullRank) throw new ArithmeticException("matrix is rank deficient");
QRDecomposition.QR qr = QRDecomposition.decompose(matrix);

try {
    QRDecomposition.QR qr = QRDecomposition.decompose(matrix);
} catch (ArithmeticException e) {
    // fall back to a rank-revealing decomposition (pivoted QR / SVD)
    qr = pivotedQrOrSvd(matrix);
}

When it happens

Trigger: Call decompose on a matrix with a duplicate column, a column that is a linear combination of previous columns, an all-zero column, or a wide/ill-conditioned matrix where numerical cancellation drives the residual to (exactly) 0.0.

Common situations: Underdetermined systems, data matrices with collinear features (common in regression datasets), a column of constants combined with another constant column, or float inputs that happen to cancel exactly.

Related errors

• Matrix A cannot be empty.
• Matrix A must be square.
• Input matrices cannot be null
• Input matrices must not be empty
• Matrices cannot be multiplied: incompatible dimensions.

AI-assisted analysis of TheAlgorithms/Java@fdfb9a395b (2026-08-13). Data as JSON: /api/errors/bf15811e934cb90b. Report an issue: GitHub.