Number of restricted integer $2\times2$ matrices with a given trace

Question

Is there a better method than bruteforcing, to find out the number of possible matrices of order $2\times2$ that have trace $N$. The contraints are that all elements in a matrix must be positive integers and the determinant of the matrix should also be positive.

Answer 1

There is always a better method than bruteforcing, hence the name "bruteforcing" - note the "brutish" part. I will assume you want more than that, although that was technically your only question... :)

Let $$A=\begin{bmatrix}a&b\\c&d\end{bmatrix}$$ Then $$a+d=N$$ That gives us the possibilities $$(a,d)=(1,N-1),(2,N-2),\dots,(N-1,1)$$ Then the determinant is $$k(N-k)-bc>0,\hspace{3mm}bc<x=k(N-k)$$ So how many pairs $(b,c)$ are there with $bc<x$ for some $x$? I think it will be $$\sum_{i=1}^{x-1}{\left[\text{ceiling}\left({x\over i}\right)-1\right]}$$

Using a computer I find this gives, for the first few values of $x$, the sequence $1, 3, 5, 8, 10, 14, 16, 20$ which is here on the OEIS.

There doesn't appear to be a simple closed form, but at least I got you pretty close.

The final answer will then be $$\sum_{k=1}^{N-1}{\sum_{i=1}^{k(N-k)-1}{\left[\text{ceiling}\left({k(N-k)\over i}\right)-1\right]}}$$

See, much better than bruteforcing!

Answer 2

To come up with a lower bound, you can assume that you choose a random splitting of $N$ into 2 positive integers for the diagonal and similarly a random splitting of $M$ for the off-diagonal where $M \leq N$, and compute what is the probability of getting a positive determinant. (Hint: It will be greater than or equal to approximately $1/2$ for large $N$). Then your lower bound for the number of matrices is essentially $1/2$ times the number of matrices you can form by splitting $N$ into two positive diagonal elements and choosing $M \leq N$ and splitting $M$ into two positive anti-diagonal elements. This gives a cubic lower bound $\Omega(N^3)$. I think the true asymptotic number of matrices that satisfy your condition is also $O(N^3)$ so at least the lower bound would be tight up to a constant factor.

Answer 3

This is the codechef problem in the current long challenge, right?? :P

Anyway, we can see that the number of matrices satisfying your conditions are the number of solutions of the equation $xy<k$ for $k={i(N-i)}$ and $i$ varies from $1$ to $(N-1)$. (Well, finding the value till $i=N/2$ suffices as it is symmetric). So, the main problem that I see here is calculating the number of solutions of $xy<k$ for some $k$.

This is a simple DP. See that once we have calculated the number of solutions of $xy<(n)$, we can get the number of solutions of $xy<(n+1)$ by just adding the number of solutions of $xy=n$, which is the number of factors of n. For an algorithm to find the number of factors of n, please look here number of factors of a given number. So, declare an array of required size and set the initial values and fill the array with

array[$i$]=array[$i-1$]+number of factors($n$)

So, the number of solutions of $xy<n$ is array[$n-1$]. The number of possible matrices would be the sum of required elements in the array.

Not the best probably, but much more efficient than the bruteforce method.

P.S: The answer is a little vague because it is a current problem in the contest. But I guess it is clear enough.

Answer 4

Let $\phi(N)$ be the sought number. Then $\phi(N)\sim \dfrac{N^3}{3}\log(N)$ (under the hypothesis that the formula of user 140943 is correct).

Proof: $\phi(N)\sim \sum_kk(N-k)\log(k(N-k))\sim\int_1^Nt(N-t)\log(t(N-t))dt\sim\dfrac{N^3}{3}\log(N)$

EDIT 1: The (140943) formula seems to be correct. On the other hand, $\phi(300)=44525297\leq \dfrac{300^3}{3}\log(300)\approx 51334042$.

EDIT 2: Some have ridiculous habit of removing a point without saying why, and without giving their name. This gives a very bad image of (pseudo ?) mathematicians.