Skip to main content
4 of 4
added 198 characters in body
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

Here is an answer. If it inspires you to change the question, please don't. Just ask a new one.

No, you can't even say that the $8$ unknowns are bounded by $T^2-1.$

To recast, given an integer matrix $A=\begin{pmatrix} a & c \\ b & d \end{pmatrix}$ with entries bounded in absolute value by $T^2,$ you wonder about finding integer matrices $W=\begin{pmatrix} w_1 & y_1 \\ w_2 & y_2 \end{pmatrix}$ and $X=\begin{pmatrix} x_1 & x_2 \\ z_1 & z_2 \end{pmatrix}$ with smaller entries and $WX=A.$

Since $\det(W)\det(X)=\det(A)$ there are constraints. For example with $T=1000$ and $p=999983$ consider

$$\begin{pmatrix} w_1 & y_1 \\ w_2 & y_2 \end{pmatrix}\begin{pmatrix} x_1 & x_2 \\ z_1 & z_2 \end{pmatrix}=\begin{pmatrix} p & 0 \\ 0 & 1 \end{pmatrix}.$$

As $p$ is prime, one of the two factors has determinant $1$, say the second. Then you can work out that

$$\begin{pmatrix} w_1 & y_1 \\ w_2 & y_2 \end{pmatrix}=\begin{pmatrix} p & 0 \\ 0 & 1 \end{pmatrix}\begin{pmatrix} z_2 & -x_2 \\ -z_1 & x_1 \end{pmatrix}=\begin{pmatrix} pz_2 & -px_2 \\ z_1 & x_1 \end{pmatrix}.$$

———

I wonder what a counting argument would give. There are about $16T^8$ ways to pick the $4$ parameters and about $256T^8$ ways to pick the $8$ unknowns. So a $16:1$ ratio. But that drops to $2:1$ once you factor in that you can swap the roles of the various $u_1,u_2$ and/or negate some pairs.

In many cases there are enormously more solutions . This should mean that other times there are none.

Also, frequently the product of two matrices with entries bounded by $T$ will contain entries larger than $T^2$ (though no larger than $2T^2.$)

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104