I solved this question in the following way:
Take an example first; N = 8
. A 2x2
matrix have determinant greater than 0
if and only if A_{11}xA_{22} > A_{12}xA_{21}, where A_{ij} is the element of the determinant and i, j = 1, 2 and A_{11} + A_{22} = N. Now we need to find all the pairs of A_{11} and A_{22} and corresponding to it all the pairs of A_{12} and A_{21} such that the above condition get satisfied. The pairs A_{11} and A_{22} for N = 8
are
1 7  7 1
2 6  6 2
3 5  5 3
4 4
Total pairs = 7. It is clear that For each of A_{11} != A_{22}, there exist two pairs and same goes for A_{12} and A_{22}. So, we need to find all the pairs for A_{12} and A_{21} corresponding to each pair of A_{11} and A_{22}. It can be observed that all the pairs of antidiagonal are same for both pair (ex: 7 1 and 1 7) of main diagonal, hence we could optimize our calculation to N/2
by calculating pairs for any one of them and then multiply it by 2
. For more clarity, I am explaining it further:
For pair 1 7 anti diagonal pairs are
1 1 1 2 1 3 1 4 1 5 1 6  Sub total = 6*2  1 = 11
2 2 2 3  Sub total = 2*2  1 = 3
. Total = 14
Now double it for both of 1 7
and 7 1
: 14*2 = 28
—> all the matrices having pair 1 7
and 7 1
as main diagonal. Similarly you can find number of matrices for 2 6
and 6 2
, 3 5
and 5 3
is equal to 2*(21+7+1) = 58
, 2*(27+11+3) = 82
respectively. Now when calculating for pair 4 4
, keep in mind that you do not have to double the total
(as I explained above, why ? ), which is 45
!
Total number of matrices = 28 + 58 + 82 + 45 = 213
.
Here is my C program implementing the above algorithm.
Feel free to ask if you find any difficulties in this algorithm :).
EDIT: While answering this I thought no need to explain about the mathematics behind it and assumed that readers will figure it out themselves, but I was wrong!
See the mathematics behind calculation of number of order pairs:
Let the final answer for a test case be total
and the partial answer for each of main diagonal pair is Sub_total
. Let x = i
and y = Ni
, where i = 1, 2, ...., N/2
, such that x+y = N
.
First we need to find total number of antidiagnol pairs for each of diagonal pair. To do this, if we divide x*y
by A_{12} and subtract A_{12}1 from it then we will get the total number of antidiagonal order pairs with that particular i
, let it be stored in count
. Keep in mind that you need to consider the even and odd behavior of x*y
. See the further explanation for more clarity:
For the above example, N = 8
, taking x = 4
and y = 84 = 4
. Here i = 4
. Now for A_{12} = 1, dividing x*y = 16
by A_{12} , i.e by 1
we will get 16 and store it in count
( count = x*y/A_{12}  (A_{12}  1) ). So the number of order pairs for A_{12} = 1 is 16 and if we calculate them manually, they are
1 1 1 2 1 3 1 4 ..... 1 14 1 15 1 16
But notice that we need to exclude the pair 1 16
as 1*16 = 16 = 4*4
and it will make the determinant of matrix to 0
. This problem comes only with even x*y
. So, for each of even x*y
we need to decrement count
by 1
(count
). By this, we have now 15
order pairs. Now just double it (2*count
) for A_{21} = 1 (no need to calculate again!!). After that we will get 30
, but here keep in mind that 1 1
is repeated twice, so again we have to decrement our 2*count
by 1
and finally we will get 29
, store it in sub_total
(sub_total = 2*count  1
).
Now similarly for A_{12} = 2, x*y/2 = 8
we will get sub_total = 2*6  1 = 11
. Here we need to exclude the pairs

2 1
, as it has already been counted in our previous calculation, and this will be done by and the subexpression A_{12}  1 in count =
x*y/A_{12}  (A_{12}  1).

2 8
, as it is equals to 4*4
, and this will be done by the expression count
for even x*y
.
 one of
2 2
pair, as it is considered twice, and will be done by sub_total = 2*count  1
.
Repeat this util you get a A_{12} such that A_{12}*A_{12} >= N
. In this case A_{12} = 4.
Now double the sub_total
if x != y
and print the total.