IntegerSolve.c

#include <stdio.h>
#include <stdlib.h>

// Helper to get/set elements in a 1D matrix (row-major)
#define MAT(m, row, col, numCols) ((m)[(row)*(numCols)+(col)])

// Swap two rows in a 1D array
void swapRows(int *matrix, int row1, int row2, int numCols) {
    for (int col = 0; col < numCols; col++) {
        int temp = MAT(matrix, row1, col, numCols);
        MAT(matrix, row1, col, numCols) = MAT(matrix, row2, col, numCols);
        MAT(matrix, row2, col, numCols) = temp;
    }
}

// Compute GCD
int gcd(int a, int b) {
    if (b == 0) return a > 0 ? a : -a;
    return gcd(b, a % b);
}

// Perform integer row reduction (not normalized RREF)
void rref_integer(int *matrix, int numRows, int numCols) {
    int lead = 0;

    for (int r = 0; r < numRows; r++) {
        if (lead >= numCols)
            return;

        int i = r;
        while (MAT(matrix, i, lead, numCols) == 0) {
            i++;
            if (i == numRows) {
                i = r;
                lead++;
                if (lead == numCols) return;
            }
        }

        swapRows(matrix, i, r, numCols);

        for (int j = 0; j < numRows; j++) {
            if (j != r && MAT(matrix, j, lead, numCols) != 0) {
                int a = MAT(matrix, r, lead, numCols);
                int b = MAT(matrix, j, lead, numCols);
                int g = gcd(a, b);

                int factor_r = b / g;
                int factor_j = a / g;

                for (int col = 0; col < numCols; col++) {
                    MAT(matrix, j, col, numCols) =
                        MAT(matrix, j, col, numCols) * factor_j -
                        MAT(matrix, r, col, numCols) * factor_r;
                }
            }
        }

        lead++;
    }
}

// Print matrix from 1D array
void printMatrix(int *matrix, int numRows, int numCols) {
    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j < numCols; j++) {
            printf("%4d ", MAT(matrix, i, j, numCols));
        }
        printf("\n");
    }
}

int main() {
    const int numRows = 9;
    const int numCols = 14;

    int test[9][14] = {
        { 2,  0,  0,  2,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0},
        { 6,  0,  2,  0,  0,  0,  1,  0,  0,  0,  0,  0,  0,  0},
        { 0,  0,  2,  0,  2,  0,  0,  1,  0,  0,  0,  0,  0,  0},
        { 0, -2,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0,  0,  0},
        { 2,  2,  0,  2,  0,  0,  0,  0,  0,  1,  0,  0,  0,  0},
        { 0,  0,  0,  0,  4,  0,  0,  0,  0,  0,  1,  0,  0,  0},
        { 3,  0,  1,  1,  1,  0,  0,  0,  0,  0,  0,  1,  0,  0},
        { 0,  2,  2,  0,  2,  0,  0,  0,  0,  0,  0,  0,  1,  0},
        { 3,  2,  1,  1,  1,  0,  0,  0,  0,  0,  0,  0,  0,  1}
    };

    // Allocate 1D matrix
    int *A = (int *)malloc(numRows * numCols * sizeof(int));
    if (!A) {
        printf("Memory allocation failed\n");
        return 1;
    }

    // Copy data
    for (int i = 0; i < numRows; i++)
        for (int j = 0; j < numCols; j++)
            MAT(A, i, j, numCols) = test[i][j];

    printf("Original matrix:\n");
    printMatrix(A, numRows, numCols);

    rref_integer(A, numRows, numCols);

    printf("\nInteger row-reduced matrix:\n");
    printMatrix(A, numRows, numCols);

    free(A);
    return 0;
}