Error finding determinant of a C++ 2 dimensional array

Question

I'm using C++ with g++ (version 13.2.1), and I am making a function Determinant<m> that accepts std::array<std::array<int,m>,m> as an argument type and returns the determinant of that matrix.

The following is the code I have written.

Determinant:

template <int m>
int Determinant(std::array<std::array<int,m>,m> arr){

    if(m == 2){
      return arr[0][0]*arr[1][1] - arr[0][1]*arr[1][0];
    }else if(m >2){
      int ans = 0;
      for(int i =0;i < m;i++){
        ans += arr[0][i]*Determinant<m-1>(slc<m,m>( arr,i,0 ))*(i%2 ? 1:-1);
      }
      return ans;
    }else{
      return -1;

    }
  }

slc : returns a slice(not really a slice, just removes a row and column)

template <int m, int n>
std::array<std::array<int,(n-1)>,(m-1)> slc(std::array<std::array<int,n>,m> arr, int i,int j){
  std::array<std::array<int,(n-1)>,(m-1)> ans;

  for(int x = 0;x < m;x ++){
    for (int y = 0;y < n;y++){
      if(y == i || x == j){
        continue;
      }
      ans[x- ( x>j ? 1:0) ][y- ( y>i ? 1:0) ] = arr[x][y];
    }
  }
  return ans;

}

The error I am getting is attached here:

matrices.cpp: In instantiation of ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 0]’:
matrices.cpp:85:42:   recursively required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 2]’
matrices.cpp:85:42:   required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 3]’
matrices.cpp:98:30:   required from here
matrices.cpp:85:51: warning: size of ‘<anonymous>’ 18446744039349813252 bytes exceeds maximum object size 9223372036854775807 [-Wlarger-than=]
   85 |         ans += arr[0][i]*Determinant<m-1>(slc<m,m>( arr,i,0 ))*(i%2 ? 1:-1);
      |                                           ~~~~~~~~^~~~~~~~~~~
matrices.cpp:85:51: warning: size of ‘<anonymous>’ 18446744039349813252 bytes exceeds maximum object size 9223372036854775807 [-Wlarger-than=]
In file included from matrices.cpp:2:
/usr/include/c++/13/array: In instantiation of ‘struct std::__array_traits<std::array<int, 18446744073709551615>, 18446744073709551615>’:
matrices.cpp:85:42:   recursively required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 2]’
matrices.cpp:85:42:   required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 3]’
matrices.cpp:98:30:   required from here
/usr/include/c++/13/array:55:13: error: size ‘18446744073709551615’ of array exceeds maximum object size ‘9223372036854775807’
   55 |       using _Type = _Tp[_Nm];
      |             ^~~~~
/usr/include/c++/13/array: In instantiation of ‘struct std::__array_traits<int, 18446744073709551615>’:
/usr/include/c++/13/array:109:55:   recursively required from ‘struct std::array<int, 18446744073709551615>’
matrices.cpp:85:42:   recursively required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 2]’
matrices.cpp:85:42:   required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 3]’
matrices.cpp:98:30:   required from here
/usr/include/c++/13/array:55:13: error: size ‘18446744073709551615’ of array exceeds maximum object size ‘9223372036854775807’
matrices.cpp: In instantiation of ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 0]’:
matrices.cpp:85:42:   recursively required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 2]’
matrices.cpp:85:42:   required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 3]’
matrices.cpp:98:30:   required from here
matrices.cpp:85:51: error: could not convert ‘slc<0, 0>(arr, i, 0)’ from ‘array<array<[...],4294967295>,4294967295>’ to ‘array<array<[...],18446744073709551615>,18446744073709551615>’
   85 |         ans += arr[0][i]*Determinant<m-1>(slc<m,m>( arr,i,0 ))*(i%2 ? 1:-1);
      |                                           ~~~~~~~~^~~~~~~~~~~
      |                                                   |
      |                                                   array<array<[...],4294967295>,4294967295>
matrices.cpp: In instantiation of ‘std::array<std::array<int, (n - 1)>, (m - 1)> slc(std::array<std::array<int, n>, m>, int, int) [with unsigned int m = 0; unsigned int n = 0]’:
matrices.cpp:85:42:   recursively required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 2]’
matrices.cpp:85:42:   required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 3]’
matrices.cpp:98:30:   required from here
matrices.cpp:6:43: warning: size of ‘ans’ 18446744039349813252 bytes exceeds maximum object size 9223372036854775807 [-Wlarger-than=]
    6 |   std::array<std::array<int,(n-1)>,(m-1)> ans;
      |                                           ^~~
matrices.cpp:15:10: warning: size of ‘<anonymous>’ 18446744039349813252 bytes exceeds maximum object size 9223372036854775807 [-Wlarger-than=]
   15 |   return ans;
      |          ^~~
matrices.cpp:15:10: warning: size of ‘<anonymous>’ 18446744039349813252 bytes exceeds maximum object size 9223372036854775807 [-Wlarger-than=]

Any insight would be greatly appreciated.

Answer 1

First of all, deduction shouldn't be possible if there is a type mismatch. int m is not the same type as m in std::array<int, m>, so you should be using:

template <std::size_t m>

Secondly, there is infinite recursion in template instantiations because you're not using if constexpr, just a regular if statement. In if (m == 2){, the code block is not discarded if the condition is false, it just becomes dead code. The same applies to the else branch.

Therefore, Determinant<2> instantiates Determinant<1>, then Determinant<0>, and then Determinant<-1> which is where you get a compiler error. To fix this, use if constexpr:

template <std::size_t m>
int Determinant(std::array<std::array<int, m>, m> arr) {
    if constexpr (m == 0) {
        return -1;
    } else if constexpr (m == 1) {
        return arr[0][0];
    } else if constexpr (m == 2) {
        return arr[0][0] * arr[1][1] - arr[0][1] * arr[1][0];
    } else {
        int ans = 0;
        for (std::size_t i = 0; i < m; i++) {
            ans += arr[0][i] * Determinant<m-1>(slc<m, m>(arr, i, 0)) * (i % 2 ? 1 : -1);
        }
        return ans;
    }
}

See also: Difference between "if constexpr()" Vs "if()"

Answer 2

Even if

if(m == 2){
  return arr[0][0]*arr[1][1] - arr[0][1]*arr[1][0];

returns a value and ends the function call, the rest of the function must still compile.

The problem is that Determinant<m-1> requires the precence of Determinant<m-1-1> which in turn requires ...

And even though the if-statements assure that those are never actually called at runtime, the code must still compile.

A common method to end the recursion is to have a specialization for a final value (0, or 2?) that is not recursive.

Answer 3

None-recursive solutions are always preferable, if available. I am not addressing the main issue in this reply; rather I just dodge the problem with an alternative approach:

#include <numeric>
#include <algorithm>

template<std::size_t N, typename E=double>
using square_matrix = std::array<std::array<E,N>,N>;

template<typename R, typename E, std::size_t N>
R   det(square_matrix<N,E> const& m){
    std::array<std::size_t,N> perm{};
    std::ranges::iota(perm, 0);
    R ret{};
    int sgn=1;
    do{
        R term = std::ranges::fold_left(
            std::views::zip_transform(
                 [](auto& row, auto& col)
                   { return R{row[col]}; }
               , m
               , perm
            ) /*zip_transform*/
          , R{sgn}
          , std::multiplies<R>{}
        ); /*fold_left*/
        sgn *=-1;
        ret += term;
    }while(std::ranges::next_permutation(perm.found);
};

This solution has famouse visual application for 3x3 and 2x2 cases, but cannot be visualized for higher dimensions. Permutations of column indice get flipping signs. For implementing slice function, I would manipulate ranges again, but that's going to be a long listing. You can temporarily use other replies to fix the slice function for inverse matrix calculations. A better aproach would be to use Gauss-Jordan algorithm to solve the equations. Determinant can be calculated as a side product of the calculations. You can apply Guass-Jordan on a unit square-matrix as the input; the output would be the inverse of coefficient matrix.