How to raise a matrix to a power with double pointers in C

Question

I am trying to raise a matrix to a power, using pointers but there is a mistake in my code I can't find.

#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
>
int **alloc(int r, int c) {
    int **d;

    d = (int **)malloc(r * sizeof(int *));
    for (int i = 0; i < r; i++) {
        d[i] = (int *)malloc(c * sizeof(int));
    }
    return d;
void input(int **A, int r, int c) {
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            printf("[%d][%d]=", i, j);
            scanf_s("%d", &A[i][j]);
        }
    }
}
void output(int **A, int r, int c) {
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            printf("%d ", A[i][j]);
        }
        printf("\n");
    }
}
void power(int **A,int**D, int r, int c,int p) {
    int i, j,k;
    for (i = 0; i < r; i++) {
        for (j = 0; j < c; j++) {
            D[i][j] = A[i][j];
        }
    }
    
    while (p) {
      // this is the matrix multiplication, where I attempt to multiply my matrix A with itself, and store the result in D, which initially started as A's copy, and p is the power I'm raising it to.
        for (i = 0; i < r; i++) {
            for (j = 0; j < c; j++) {

                for (k = 0; k < c; k++)
                    D[i][j] = D[i][j] + A[i][k] * D[k][j];
            }
        }
        p--;
    }
} 
void main() {
    int r, c;
    int **A, **D;

    printf("rows A: ");
    scanf_s("%d", &r);
    printf("columns A: ");
    scanf_s("%d", &c);
    
    A = alloc(r, c);
    

    printf("\nValues of A:\n");
    input(A, r, c);
    printf("\nMatrIX A is:\n");
    output(A, r, c);


    D = alloc(r, c);
    printf("input the value you want to raise your matrix to: ");
    int p;
    scanf_s("%d", &p);
    power(A, D, r, c, p);
    printf("\nMatrix raised to said power is:\n");
    output(D, r, c);

    _getch();
}

When I input the rows and columns as 2 each, and input all values in the matrix as 1 and raise it to the power of 3, my answer should be

4 4
4 4

instead of

72 72
232 232

What is wrong in my code? If I were to print the D matrix before the multiplication, it would print it correctly, as:

1 1
1 1

Answer 1

Your two-step allocation looks okay, except that you don't free the memory after you're done. Your problem is in how you multiply the matrix:

• Raising a matrix to a power involves multiplying it to itself. You can only do that if the matrix is square. You can replace all occurrences of rows r and columns c with a single dimension n.

• When you do the actual multiplication:

   D[i][j] = D[i][j] + A[i][k] * D[k][j];
  

  you assign to D and read from it at the same time. Subsequent calculations (of the same multiplication) will see a changed value of D[i][j]. You will need a temporary "scratch" matrix.

• Your code multiplies once too many. Also, Raising a matrix to the power of zero should yield the identity matrix.

Here's how your power function could look like:

void power(int **A, int **D, int n, int p)
{
    int i, j,k;

    // assign identity matrix to result D

    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            D[i][j] = (i == j);
        }
    }
    
    // create a scratch matrix
    
    int **tmp = alloc(n);
    
    while (p-- > 0) {
    
        // multiply [tmp] = [A] * [D]
    
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                tmp[i][j] = 0;

                for (k = 0; k < n; k++)
                    tmp[i][j] += A[i][k] * D[k][j];
            }
        }
        
        // copy [D] = [tmp]
        
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                D[i][j] = tmp[i][j];
            }
        }
    }
    
    // TODO: clean up the scratch matrix
}