The distributional matrix correspondence problem concerns
with 
unimodular matrices,
where a square matrix 
is unimodular if all entries in are
integers and its determinant 
. For convenience, when we mention
unimodular matrix in this paper we mean that its dimension is
two-by-two.
Let 
denote the
set of unimodular matrices.
Define the size of a unimodular matrix , denoted by 
,
to be the length
of the binary representation of the maximal absolute value
of its entries.
It can be shown that the uniform probability
of choosing of size 
among all positive unimodular
matrices is 
.
DISTRIBUTIONAL MATRIX CORRESPONDENCE PROBLEM
Instance. A unimodular matrix 
, a list 
of unimodular matrices, and a positive
integer 
. The size of the instance is 
.
Question. Are there unimodular matrices 
(by matrix multiplication)
and 
, where 
and
,
such that 
? (If such and 
exist, then we say that
the instance has a solution of length at most .)
Distribution.
Randomly and independently choose positive integers and 
with respect to the default uniform distribution, then
randomly and independently choose unimodular matrices
. Hence, the probability distribution
is proportional to
In the definition of the distributional matrix correspondence problem, if we only allow positive unimodular matrices, where by ``positive" we mean that every entry is a positive integer, then we obtain the DISTRIBUTIONAL POSITIVE MATRIX CORRESPONDENCE PROBLEM.
The distributional matrix correspondence problem was shown to be average-case NP-complete by Gurevich [Gur90] under a randomized reduction (see also [BG95]).