The distributional
matrix transformation problem was first shown to be complete for
DistNP by Gurevich [Gur90] (see also [BG95]). The proof
presented here is based on the proof given in [BG95].
Recall that a linear transformation is a function 
such that 
whenever
all the 
and 
are unimodular matrices.
We first show that a linear transformation can be represented by
a 
integer matrix, and that given a integer matrix,
it is decidable in polynomial time whether it represents a linear
transformation.
Let 
be one of the following class of numbers:
(the rationals), 
(the real numbers),
and 
(the complex numbers).
Let 
denote the vector space of two-by-two matrices with entries
in . The definition of
linear transformations on is the standard one. Namely,
a linear transformation on is a function
such that
for all 
and 
,
and 
.
Let 
denote the multiplicative group of two-by-two matrices 
with entries
in such that 
.
For any two-by-two matrix , write
.
Proof.. Without loss of generality, we assume that 
.
Next, we show that 
can be extended to a linear
transformation 
on 
.
Let 
.
The standard basis for (
) is the set of the following four matrices:
It is an easy exercise to verify that
any of these matrices is a linear combination (with integer
coefficients) of the matrices in 
. Thus,
is also a basis for .
The linear extension on 
is the linear transformation
that agrees with on the four matrices in .
Note that for 
,
because 
, and so
it is easy to see that agrees with on
and that is unique.
From now on, we write not only for the given linear transformation
but also for . It is easy to see that if a matrix 
has integer entries then so does 
.
Next, we show that preserves determinants. Namely,
for all , 
.
This is true for by the definition of .
So we consider .
Note that 
,
where 
and 
.
Thus, (1) there are at least two distinct
nonzero such that 
iff (2) 
.
Clearly, if satisfies condition (1), then so does
since
iff 
iff 
.
Let 
be the set of matrices in
satisfying condition (1), or (2)
equivalently. Then is closed under .
Therefore, the linear span 
of
is also closed under . Note that the trace of every matrix in
is zero and that matrices with zero trace form
a three-dimensional subspace of .
Since contains the matrices 
, 
, and
,
it follows that is exactly that
three-dimensional subspace. is a cone in the three-dimensional
vector space .
We now show that there is a 
such that
for all 
with 
,
.
Let 
, then 
. Let 
and 
. Then
. Since is linear and 
is quadratic, 
for some coefficients 
.
By assumption, . If
is also equal to 
, then 
has to be zero
as discussed above. Choose 
and 
make
and so 
. It follows that
for all 
.
It follows that 
and 
.
Hence, 
.
To find out the value of 
, consider 
with
and
. So 
. It follows that 
.
We have therefore shown that for all with
, .
For with 
, we can
write 
, where and 
.
As we have shown above, 
and so 
.Thus,
.
The completes the proof of part 1.
2. As indicated in [BG95], the proof of part 2 can also be
found from [Wae35].
We consider the complex vector space , and we
use the following basis for this space:
This basis gives a very simple formula for determinant:
.
Since is linear and preserves determinants and 
, it is easy to see
that 
iff 
and so
also preserves eigenvalues. In particular,
has eigenvalues 0 and 1. We can view
as a
transformation of two component vectors, which is a projection
onto some line along some other line, and so it has the form
for some 
. Since the eigenvalues are 0 and 1,
the trace is 1, and so 
.
Let 
,
then 
. Note that 
.
Let 
, then clearly 
and
. Since 
, 
.
Clearly, if we can show part 2 for 
with matrix 
, then the same
result is true for with matrix 
. So without loss of
generality, we assume that also preserves and 
.
Let
then there are 
such
that 
.
By part 1, for all , so
. Note that also
preserves and , so it must leave invariant the set of
vectors orthogonal to both and , namely, the linear span
of 
and 
. Hence, we have 
for some 
.
We also have 
. There is
a complex number 
such that 
.
Note that 
, so 
.
Replacing with 
if necessary, we have
and 
.
Let 
, and let 
. Then
.
So 
.
Note that 
.
Let 
, then 
.
Clearly, also preserves and . Similar to what
we discussed before, we can simply assume that preserves as
well.
It follows that fixes the subspace orthogonal to , , and 
.
So 
for some . Since 
, 
. If 
, then preserves
all four basis matrices, and so is the identity.
If 
, we note that 
,
, and 
, and so
for all .
We now return to the original which is normalized to preserve and
extended to , and we have just shown that there is
a 
such that either for all ,
or for all ,
or 
. We also know that if
the entries of are integers then so are those of .
We are left to show that there are 
such that part 2 of the lemma holds.
Without loss of generality, we assume that .
The other case is similar.
Write 
.
Then since 
, 
.
Let be the matrix with a single entry equal to 1
and all other entries zero. then the entries of
are all integers which are products of two entries of 
.
By considering all four possible locations of the entry 1, we obtain
all possible products of any two entries of , which are all integers.
In particular, the square of each entry of is an integer.
So each entry of can be written in the form
, where 
is either 
or 1, 
,
and is either 
or is a square root of a positive,
non-square number.
We first show that has to be equal to 1. If not, then must
contain 
as a factor for some prime number 
. It follows
that has to be a factor
of every other non-zero entry because the product of one number with
as a factor and one without cannot be an integer.
Hence, divides , which is impossible.
If 
in one entry, then
must be in every non-zero entry because the product of
one number with and one without cannot be an integer.
Let 
and 
.
If 
, then let 
and 
.
This completes the proof of part 2.
Let be a linear transformation on . By
Lemma 6.26, can be uniquely extended to a
linear transformation on . For convenience, we
still call this extension . Let
By Lemma 6.26(1), 
is a four-by-four matrix with
integer entries. Also, it is easy to see that
Let be four-by-four matrix with , we have
.
This implies that 
.
In Lemma 6.26(2), is called a right (respectively, left)
transformation in the first (respectively, second) case.
Using the fact that
, it is straightforward
to show is a right transformation
iff 
.
Proof.first calculate 
. If 
, then 
does
not represent any linear transformation. Assume that 
.
The case that 
is similar. Then might
represent a linear transformation such that there are
and 
in such that for all ,
. Note that for any and in ,
is a linear transformation.
We will show how to find and .
Let 
and 
.
If represents , then
We can recover all 
and all 
from . Thus,
we can recover and up to a scalar factor. Using
the fact that we can find and .
Hence, we can determine whether 
for some
in polynomial time.
For convenience, we may
ignore the distinction between a linear transformation
on and its matrix representation
due to Lemmas 6.26 and 6.27.
For , let 
be the linear
transformation such that 
for all .
Proof.will reduce the distributional matrix correspondence problem
to the distributional matrix transformation problem.
Let 
be an instance of the distributional matrix correspondence.
Let 
be the result of replacing each pair 
in 
with the linear transformation .
Define a reduction 
by 
.
Clearly, 
iff 
.
We are only left to verify the domination property. It suffices to
show that the distribution of 
dominates the
distribution of . Recall that since 
,
has the same entries
as those of except for the signs and locations. So
. Hence,
.
Let 
and 
. Then
.
Let 
.
Then the number of four-by-four
matrixes of size 
is
Hence, the distribution of 
is proportional to
.
Note that
the distribution of pair is
, which is dominated by the distribution
of . This completes the proof.
