The distributional matrix transformation problem
concerns with linear transformations on unimodular matrices.
A linear transformation of 
is
a function 
such that 
whenever all the 
and 
are unimodular matrices.
(Note that is not closed under
addition in general.)
A linear transformation of
can be represented by a 
integer
matrix, and it is decidable in polynomial time whether
a given integer matrix represents a linear transformation
of [BG95].
Let 
be a linear transformation and let 
be its
four-by-four integer matrix representation.
Define the size of
to be the length of the largest absolute value (in the binary notation) of
entries in . It can be shown that the uniform
distribution of among all linear transformations of size 
is
.
DISTRIBUTIONAL MATRIX TRANSFORMATION PROBLEM
Instance. A unimodular matrix 
, a finite set 
of linear
transformation of unimodular matrices, and a
natural number 
. The size of the instance
is plus the size of plus the sum of the sizes
of all members in .
Question. Does a linear transformation exist,
where 
, 
,
, such that 
is the identity matrix?
Distribution.
The three components are chosen randomly and independently.
The integer
component is chosen with respect to the default uniform
distribution
. The unimodular component is chosen with
probability 
.
Linear transformations are chosen with respect to the
uniform distribution on transformations of the same size.
Finally, the probability
of is proportional to the product of the probabilities
of the members in .
The distributional matrix transformation problem was
shown to be average-case NP-complete by
Gurevich [Gur90] and a full proof was published
by Blass and Gurevich [BG95] using a randomized reduction.