Distributional Matrix Correspondence

The distributional matrix correspondence problem was first shown to be complete for DistNP by Gurevich [Gur90]. A detailed proof was given in [BG95]. The proof presented here is based on [BG95].

Recall that we use to denote the set of unimodular matrices, and a unimodular matrix is a two-by-two matrix of integer entries such that . A matrix is represented by a list of its entries in binary notation. We begin with a discussion on positive unimodular matrices.
Positive matrices

A unimodular matrix is called positive if it has no negative entries. Positive matrices form a monoid while forms a multiplicative group called modular group. In this section, by a column we mean a column of two relatively prime nonnegative integers. We may view a positive matrix as the pair of its columns. If is a column, we use to represent the upper and the lower components of . Let and be two columns. Write if and , and write if and either or . Define to be the maximal entry of a positive matrix . Let

Proof.(1) is obvious. For part (2), note that if , then from (1), so . For part (3), if occurs twice in the same row or the same column, then divides and so . Otherwise, we first note that the determinant being positive implies that cannot occur on and , so the only case left is . In this case, and so .

Proof.that Lemma 6.14(2) implies that and generate a free monoid. Also note that forms a free monoid on the operation of concatenation. So it suffices to show that every non-unit positive matrix is a product of and . Define and . We prove the lemma by induction on . Since the entries of the main diagonal cannot be 0, . Note that and are the only non-unit matrices of weights . So the case is obvious. Suppose . Then . We assume that occurs in , the case that occurs in is similar. If , then and so . Similarly, if then . Thus, the column has nonnegative entries and so . Since , . By the induction hypothesis, is a product of matrices and . By Lemma 6.14(1), .

We call the greater column of a non-unit positive matrix is called the major column. In the case of the unit matrix, we call either column major. The other column is call minor.

Proof.loss of generality, assume that is not the unit matrix. It follows that both components of the major column are positive. Suppose that is the major column (the case that is the major column is similar). We will show that is the least column such that . Let be any column such that . Then for some because and are relatively prime. Hence, and . If , then either or is negative. Thus, and therefore , . The minor column can be found in polynomial time by using the extended Euclid's algorithm [Knu73].

Let be a natural number. Denote by the length of the binary notation of . Let be a positive matrix, and .

Proof.suffices to prove that the number of positive matrices of size is . Let denote the number of positive integers that are prime to , and . Then . Thus, .

There are exactly two isomorphisms of to . One takes to 0 and to 1, denoted by , and the other one takes to 1 and to 0. Let denote the isomorphism from to . By an induction on the length of , it is easy to check that if starts with 0 (respectively, 1), then the lower (respectively, upper) row of is major. Note that the size of a matrix may not be polynomially related to the length of the corresponding string . For example, a matrix whereas . This implies that is not p-time computable. However, we can show that is ap-time computable. Let be a positive matrix. Denote by the probability distribution of which is proportional to by Lemma 6.17. Let be proportional to . .

Proof. be a positive matrix, then can be computed by the following recursive algorithm. If is the unit matrix then is the empty string (the identity of the monoid ). Suppose that differs from the unit matrix. If is the major column, let and , then . If is the major column, let and , then . This algorithm runs in time proportional to . Next, we show that is polynomial on -average.

Suppose that is a nonempty binary string and let be the two entries of the major row of . First, we note that can be uniquely represented by a finite continued fraction , where is a nonnegative integer, with is a positive integer, and is an integer . In other words, , where , , , , , . This fact is true for any positive rational number and its proof can be found numerous number theory books such as [HW88][Ste69].

Let . Then by an induction on , we can show that . If , then and . Suppose . Assume that . The case that is similar. Let be the major row of . Then by Lemma 6.14 and Remark 6.4. It suffices to show that if , then , and if , then . Since is not the unit matrix, neither nor is zero. In any case, . If , write , then , so . If , write , then , so .

Yao and Knuth [YK75] showed that, for any positive integers ,

Let , and form the major row of . Therefore, . Then and so . By Lemma 6.17, , so . It follows that is polynomial on -average.

The isomorphism is p-time computable but the distribution does not dominate the distribution with respect to . Thus, fails to reduce to .

Proof., to the contrary, that is (weakly) dominated by with respect to . Since is one-one, there is a function such that is polynomial on -average. Thus, there is an such that

Hence, . We will show that this is impossible.

Let . By the definition of and Lemma 6.17, . Let be the sum of the entries of the major row of . Clearly, . Hence, it suffices to show that the expectation is not bounded by any polynomial of . We may restrict our attention to . Let and range over strings of length .

Define . Then there exists an such that for every , . To see this, let be the two entries of the major row of , and . Then

Let . Then . Consider the function . Note that , so . Thus, is concave. Since , the chord between the points and lies strictly above the chord between the points and . Clearly, the center of the interval coincides with the center 1.5 of the interval [1,2], and so the center of lies directly above the center of . Note that the arithmetical mean of numbers 1 and exceeds their geometrical mean . Thus, . The desired is . Thus,

It follows that () and therefore is not bounded by any polynomial of .

Positive Matrix Correspondence

Let be a nondeterministic Turing machine. Let , and be proportional to . The size of is . From the proof of Theorem 4.1, it is easy to see that there is a Turing machine such that is complete for DistNP. Moreover, we can assume that accepts iff halts on . Let be a distribution proportional to .

Proof.will reduce to an appropriate . One might be tempted to simply take and to use the identity function as a reduction. By Proposition 6.19, this approach fails to meet the domination requirement.

For every binary string , let be the positive integer with binary representation . If , let . We construct such that, on any input , first computes , then simulates on .

Define a good-input domain such that for all ,

where represents the greatest common divisor of and . Clearly, is certifiable. Let be the number of positive integers that are relatively prime to and less than . Then [HW88]. Note that if , then so is provided that . Hence, half of the integers counted by , and so . Thus,

Therefore, the rarity function , which implies that is nonrare.

By Lemma 6.16, for each , there is a unique positive matrix with being its first and major column. Define the reduction by

where and is the time that needs to convert into .

By the definition of , it is easy to verify that halts on iff halts on in steps iff halts within steps on iff halts on . So for all , iff .

Next, we check that is ap-time computable with respect to . Since , can be computed in time polynomial on -average. Now we consider , which is the time that needs to compute from . Clearly is bounded by a polynomial of since , , and are all p-time computabl e. It follows that is polynomial on -average.

We now check that satisfies the domination property. Note that is one-one and so we can use Lemma 2.1. We have . Note that , , and , so .

Similar to the proof of Theorem 5.2, it is straightforward to reduce to the distributional positive matrix correspondence problem by taking in that proof. The reduction is given by , where represents the instance of of . The isomorphism carries out the entire proof into the matrix setting. This provides a proof to the following theorem.

Matrix Correspondence

We now turn our attention to unimodular matrices that may or may not be positive. The technical terms we used to describe positive matrices such as major columns, major rows, and the size of the matrix will apply to unimodular matrices with respect to absolute values. In this part, we use to represent absolute value unless otherwise stated. Let be a column. Denote by the column of and , and . Let be a unimodular matrix. Write .

Proof.. If one of the numbers and is positive and the other is negative, then , which is impossible. If the two numbers are both positive, then ; otherwise, .

2. Suppose that is not one of the four matrices listed, and suppose that neither nor . Without loss of generality, assume that and . (The other case is similar.) Clearly, either or . Hence, by assumption, , a contradiction.

3. Suppose, to the contrary, that has two or more entries with value . If occurs in both entries in the same row or in the same column, then divides , which is impossible. Thus, suppose that occurs exactly twice in different columns and different row. Without loss of generality, assume that it occupies the second diagonal, i.e., . (The other case is similar.) If , then the determinant is negative, which is a contradiction. Hence, . By part 1 above, and , a contradiction.

Proof.first show that for every two unimodular matrices and , there is an integer such that . Suppose (the case that is similar). Then , and so . Let to obtain the claim. Suppose , then , and do for some . The claim is therefore obvious.

To prove the lemma, it suffices to consider the case when is the major column. (If instead is the major column, then the unimodular matrix will have the major column on the left.) Moreover, it suffices to consider that is positive, for otherwise, the unimodular matrix will have the major column on the left and the major column is positive. Let be the major entry of , i.e., . Let be another matrix with major column . Then as seen above, there is a such that . Since , . If , then ; if , then . Note that if (respectively, ) then is the major column of (respectively, ). Since by assumption that is positive, and . By Lemma 6.22(1), is either positive or negative. If is positive (respectively, negative), then is negative (respectively, positive).

The size of a unimodular matrix , denoted by , is defined to be the length of in binary notation. We assume that all unimodular matrices of the same size have an equal chance to be selected.

Proof. be the collection of unimodular matrices with . Let be the collection of matrices such that the major row of is positive. For every , exactly one of the two matrices and belongs to . It remains to show that the probability of a random matrix from being positive is . Since the major component of an matrix is greater than 1, the minor component of the major column cannot be zero. Let be the collection of matrices such that the minor component of the major column is positive. For every matrix , let be the result of multiplying by the diagonal of that contains the minor component of the major column. Exactly one of the two matrices , belongs to . It follows that contains exactly one half of the elements of . By Lemma 6.23, the probability of a random matrix being positive is .

Clearly, the identity function reduces the distributional positive matrix correspondence problem to the distributional matrix correspondence problem.