REPRESENTING INTEGERS IN THE BINARY NUMBER SYSTEM AS PERMANENTS OF CERTAIN MATRICES

Seol Han–Guk

Abstract. The permanent of an m–by–n matrix A is the sum of all possible products of m elements from A with the property that the elements in each of the products lie on different lines of A. This scalar valued function of the matrix A occurs throughout the combinatorial literature in connection with various enumeration and extremal problems. In this note, we construct a (0, 1)–matrix with a prescribed permanent, 1, 2, …, 2^{n−1}.

1. Introduction. Let A = [a_{ij}] be an m–by–n matrix. The permanent of A is defined by

per(A) = ∑ a_{1i_{1}}a_{2i_{2}} ⋯ a_{mi_{m}},

where the summation extends over all the m–permutations (i_{1}, i_{2}, …, i_{m}) of the integers 1, 2, …, n. Thus, per(A) is the sum of all possible products of m elements of the m–by–n matrix A with the property that the elements in the product comes from different columns of A. This scalar valued function of the matrix A occurs throughout the combinatorial literature in connection with various enumeration and extremal problems. In [1], it was shown that the existence of the (0, 1)–matrix of order n whose permanent is k (0 ≤ k ≤ 2^{n−1}). In this note, we construct a (0, 1)–matrix whose permanent is k (0 ≤ k ≤ 2^{n−1}) by the binary number system of k. Its related matrices are also considered.

2. Construction of (0, 1)–Matrix with Permanent k. For the purpose of our construction, we define the following matrix.

\underline{Definition 1}. Let B_{n} be the following n–by–n (0, 1)–matrix.

B_{n} = [b_{ij}] = [ \begin{matrix}1 & 1 & 1 & 1 & · & · & · & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & · & · & · & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & · & · & · & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & · & · & · & 0 & 0 & 0 & 0 & 0 \\ · & · & · & · & · & · & · & · & · & · & · & · \\ · & · & · & · & · & · & · & · & · & · & · & · \\ · & · & · & · & · & · & · & · & · & · & · & · \\ · & · & · & · & · & · & · & · & · & · & · & · \\ 1 & 1 & 1 & 1 & · & · & · & 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & · & · & · & 1 & 1 & 1 & 1 & 1 \end{matrix} ] .

We say B_{n} is the basic matrix of order n.

Let A = [a_{ij}] be an m–by–n real matrix with row vectors α_{1}, α_{2}, …, α_{m}. We say A is contractible on column (row) k if column (row) k contains exactly two nonzero entries. Suppose A is contractible on column k with a_{ik} ≠ 0 ≠ a_{jk} and i ≠ j. Then the (m − 1)–by–(n − 1) matrix A_{ij:k} obtained from A by replacing row i with a_{jk}α_{i} + a_{ik}α_{j} and deleting row j and column k is called the contraction of A on column k relative to rows i and j. If A is contractible on row k with a_{ki} ≠ 0 and a_{kj} ≠ 0 for some i ≠ j, then the matrix A_{k:ij} = [A_{ij:k}^{T}]^{T} is called the contraction of A on row k relative to columns i and j. Now we can evaluate the permanent of B_{n}.

\underline{Lemma 1}. perB_{n} = 2^{n−1}.

\underline{Proof}. By the contraction of B_{n} on column n relative to rows 1 and n, perB_{n} = 2perB_{n−1}. Since perB_{2} = 2, it follows by induction that perB_{n} = 2^{n−1}. The proof is complete.

In addition, we may define a related matrix using B_{n}.

\underline{Definition 2}. B_{n}(n, k) = B_{n}−E_{n,k}, where E_{n,k} is a cell which is a (0, 1)–matrix with only one entry equal to 1, the (n, k) entry.

\underline{Definition 3}. B_{n}(n|k) is the submatrix of B_{n} whose nth row and kth column are deleted.

\underline{Proposition}. perB_{n}(n, k) = 2^{n−1} − 2^{k−2}, (k = 2, 3, …, n) and perB_{n}(n, 1) = 2^{n−1} − 1.

\underline{Proof}. It easily follows that perB_{n}(n|k) = 2^{k−2}, k = 2, 3, …, n, and perB_{n}(n|1) = 1. Since perB_{n}(n, k) = perB_{n} − perB_{n}(n|k), perB_{n}(n, k) = 2^{n−1} − 2^{k−2}, k = 2, 3, …, n and perB_{n}(n, 1) = 2^{n−1} − 1. The proof is complete.

Now we define the process of the construction of a (0, 1)–matrix by the binary number system (base 2), and give the main result.

\underline{Definition 4}. Let t be a positive integer with 2^{n−2} ≤ t ≤ 2^{n−1} and t_{(2)} = x_{n−2}x_{n−3} ⋯ x_{1}x_{0} be the binary representation of t, where the x_{i}’s are 0 or 1. Define x_{k}^{c} = 1 if x_{k} = 0, and 0, otherwise.

\underline{Theorem}. Let t be a positive integer with 2^{n−2} < t ≤ 2^{n−1} and t_{(2)} = x_{n−2}x_{n−3} ⋯ x_{1}x_{0} be the binary representation of t. Let B_{n}(t) be obtained from B_{n} by replacing b_{n,k} to x_{k−1}^{c}, for all k = 1, 2, …, n − 1. Then perB_{n}(t) = 2^{n−1} − t.

\underline{Proof}. Let t_{(2)} = x_{n−2}x_{n−3} ⋯ x_{1}x_{0}. Then t = x_{n−2}2^{n−2} + x_{n−3}2^{n−3} + ⋯ + x_{1} + x_{0}. By the expansion of the nth row of B_{n}(t),

per(B_{n}(t)) = ∑_{k=1}^{n} b_{nk}perB(n|k)

= perB(n|1) + ∑_{k=2}^{n} x_{k−2}^{c}perB(n|k) + perB(n|n)

= 1 + ∑_{k=2}^{n} x_{k−2}^{c}2^{k−2} + 2^{n−2}

= 2^{n−1} − ∑_{k=2}^{n} x_{k−2}2^{k−2}

= 2^{n−1} − t.

The proof is complete.

\underline{Example}. Let k = 389. Then

B_{10} = [ \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix} ] ,

with permanent 512 = 2^{9}. Take t = 123. Then (123)_{(2)} = 01111011. Then

B_{10}(123) = [ \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \end{matrix} ]

and perB_{10}(123) = 512 − 123 = 389.

\underline{Conclusion}. For any positive integer k, we can find a (0, 1)–matrix with permanent k, (1, 2, …, 2^{n−1}).

3. Some Results for Related B_{n}. Now we may consider the permanent of matrices by replacing 0 entries in B_{n} by 1. The following theorem contains properties of permanents for matrices which are related to B_{n}. Recall that matrix E_{i,j} is a cell with appropriate size.

\underline{Theorem}.

(1) per(B_{n} + E_{2,k}) = 2^{n−k}per(B_{k} + E_{2,k}), (k = 3, 4, …, n − 1).

(2) per(B_{n} + E_{2,n}) = 2perB_{n−1} + per(B_{n−1} + E_{2,3} + E_{3,4} + ⋯ + E_{n−2,n−1}).

(3) per(B_{n} + E_{2,3} + E_{3,4} + ⋯ + E_{n−1,n}) = 2 × 3^{n−2}.

(4) per(B_{n} + E_{3,k}) = 2^{n−k+1}per(B_{k−1} + E_{2,k−1}), (k = 4, 5, …, n − 1).

(5) per(B_{n} + E_{k,n}) = 2^{k−2}per(B_{n−k+2} + E_{2,n−k+2}), (k = 3, 4, …, n − 1).

\underline{Proof}.

(1) By contraction of B_{n} +E_{2,k} on column n relative to rows of 1 and n, we obtain per(B_{n} + E_{2,k}) = 2per(B_{n−1} + E_{2,k}), where the order of E_{2,k} is n − 1. Now we apply this process to B_{n−1} + E_{2,k} of order n − 1. Then per(B_{n} + E_{2,k}) = 2^{n−k}per(B_{k} + E_{2,k}), (k = 3, 4, …, n − 1).

(2) Expanding the second row of (B_{n} + E_{2,n}), we obtain per(B_{n} + E_{2,n}) = 2perB_{n−1} + per(B_{n−1} + E_{2,3} + E_{3,4} + ⋯ + E_{n−2,n−1}).

(3) Expand the second row of per(B_{n} + E_{2,3} + E_{3,4} + ⋯ + E_{n−1,n}) = 3per(B_{n−1} + E_{2,3} + E_{3,4} + ⋯ + E_{n−2,n−1}). Continuing this process, we obtain the matrix J_{3} with permanent equal to 3!.

(4) Contracting B_{n} + E_{3,k} on row 2 relative to columns 1 and 2, we have that per(B_{n}+E_{3,k}) = 2per(B_{n−1}+E_{2,k−1}). Now applying formula (1) to the matrix B_{n−1} +E_{2,k−1}, we have that per(B_{n−1} +E_{2,k−1}) = 2^{n−k−2}per(B_{k−1} +E_{2,k−1}).

(5) Contracting B_{n} + E_{k,n} on row 2 relative to columns 1 and 2, we have that per(B_{n} + E_{k,n}) = 2per(B_{n−1} + E_{k−1,n−1}). Continuing this process, we obtain the matrix B_{n−k+2} + E_{2,n−k+2}. This leads us to the conclusion.

The proof is complete.

Mathematics Subject Classification (2000): 15A15

\underline{Reference}

1. R. A. Brualdi and H. A. Ryser, Combinatorial Matrix Theory, Cambridge University Press, 1991.

Seol Han–Guk Department of Mathematics Daejin University Pocheon 487-711 Korea email: hgseol@skku.edu