How to calculate the number of factorizations of a square matrix?

I need to write a function, that, given a square matrix M of non-negative integers, calculates the number of representations of M as a product of two square matrices of non-negative integers. Could you please help me with it?

Solution 1:

The considered function (denoted by $f$) has values in $\mathbb{N}\cup \{+\infty\}$. Indeed, let the following non-invertible matrix $A=\begin{pmatrix}2&3\\6&9\end{pmatrix}$. One has $A=\begin{pmatrix}3&1\\\alpha&3\end{pmatrix}\begin{pmatrix}0&0\\2&3\end{pmatrix}$.

EDIT: OK OL, I can do better.

Prop: if $A$ is invertible, then $f(A)$ is finite. Morover the proof gives a procedure (certainly not the best but it's better than nothing) to calculate $f(A)$ in this case.

Proof: 1. Let $A=BC$ be an acceptable decomposition with $A=[a_{i,j}],\cdots$. Consider the entry $b_{i,j}$. Since $C$ is invertible, there is $k$ s.t. $c_{j,k}\geq 1$. One has $b_{i,j}\leq b_{i,j}c_{j,k}\leq a_{i,k}\leq \sup_l(a_{i,l})=||A_i||_{\infty}$ where $A_i$ is the row-vector of $A$ of index $i$. 2. Naive Procedure: Test all the matrices $B$ s.t. $0\leq b_{i,j}\leq ||A_i||_{\infty}$, the condition to satisfy being

(COND): $\det(B)$ is non-zero and is a divisor of $\det(A)$ AND $B^{-1}A$ is a matrix of non-negative integers.