# On a Property of a Three-Dimensional Matrix

Authors: David Blokh
Journal: Journal of Discrete Mathematics
 (2013)

---

## Abstract

LetSn  be the symmetrical group acting on the set 1,2,…,n and x,y∈Sn. Consider the set W={(i,x(i),y(i))∣1≤i≤n,|i-x(i)|>1∨|i-y(i)|>1∨|x(i)-y(i)|>1}. The main result of this paper is the following theorem. If the number of W set entries is more than [n/3], then there exist entries (i1,x(i1),y(i1)),(i2,x(i2),y(i2)),(i3,x(i3),y(i3))∈W such that |i1-x(i2)|≤1, |i1-y(i3)|≤1, and  |x(i2)-y(i3)|≤1. The application of this theorem to the three-dimensional assignment problem is considered.


---

## Body

## 1. Introduction

LetRn3 be the set of n×n×n-matrices over the field of real numbers.Three-dimensional matrix not only is an interesting mathematical object [1–3], but also has applications in many fields, such as theoretical physics [4] and operational research [5, 6].LetSn be the symmetrical group acting on the set {1,2,…,n}, x,y∈Sn, ∥aijk∥∈Rn3 and
(1)G={aijk∣|i-j|≤1∧|i-k|≤1∧|j-k|≤1},H={aijk∣|i-j|>1∨|i-k|>1∨|j-k|>1},T={aix(i)y(i)∣1≤i≤n}.The main result of this paper is the following theorem.Theorem 1.
If∥aijk∥∈Rn3, x,y∈Sn and the number of T∩H set entries is more than [n/3], then there exist entries ai1j1k1,ai2j2k2, and ai3j3k3∈T∩H such that the entry ai1j2k3∈G.We give another formulation of Theorem1.Consider the set(2)W={(i,x(i),y(i))∣1≤i≤n,|i-x(i)|W=55>1∨|i-y(i)|>1∨|x(i)-y(i)|>1}.Theorem 2.
If the number ofW set entries is more than [n/3], then there exist entries (i1,x(i1),y(i1)),(i2,x(i2),y(i2)),(i3,x(i3),y(i3))∈W such that |i1-x(i2)|≤1, |i1-y(i3)|≤1, and  |x(i2)-y(i3)|≤1.


## 2. Proof of Theorem1

We prove the theorem by contradiction. The set of matrix∥aijk∥∈Rn3 entries with one index fixed and the two others having values from 1 to n will be called a layer. We denote a layer by Lsr, where r indicates the location of a fixed index and s indicates its value. For example, Ls2={aisk∣i,k=1,…,n}. Furthermore, entries from G will be called basic, entries from H will be called nonbasic; T will be termed a trajectory; the layer containing a basic trajectory entry will be termed a basic layer and the layer containing a nonbasic trajectory entrywill be termed a nonbasic layer.IfLs1 is a nonbasic layer, then one layer in the pair Ls-12,Ls-13 is basic.Suppose to the contrary that layersLs1, Ls-12, and Ls-13  are nonbasic. Let asj1k1, ai2,s-1,k2, and ai3,j3,s-1 be the trajectory entries of Ls1, Ls-12, Ls-13 layers. Replace asj1k1,ai2,s-1,k2, and ai3,j3,s-1 with as,s-1,s-1, ai2j1k1, and ai3j3k2. The nonbasic trajectory entries asj1k1,ai2,s-1,k2, and ai3,j3,s-1 are replaced with entries as,s-1,s-1, ai2j1k1, and ai3j3k2, among which there is a basic one.Similar assertions may be proved for theLs1 layer and the following layer pairs: Ls-12,Ls3; Ls2,Ls-13; Ls2,Ls3; Ls2,Ls+13; Ls+12,Ls3; and Ls+12,Ls+13.Three nonbasic layers may not be consecutive.Suppose that layersLs-11, Ls1, and Ls+11 are nonbasic. One of the layers Ls2 or Ls3 is basic. In these layers, the basic entries may be as-1,s,s-1, as-1,s,s, as,s,s-1, asss, as,s,s+1, as+1,s,s, and as+1,s,s+1 for the layer Ls2, and as-1,s-1,s, as-1,s,s, as,s-1,s, asss, as+1,s,s, as,s+1,s, as+1,s+1,s for the layer Ls3. However, this contradicts the assumption that the layers Ls-11, Ls1, and Ls+11 are nonbasic. The fact that the two first and the two last layers may not be nonbasic is proved in a similar way.All assertions given below represent conditions that prevent replacing nonbasic trajectory entries with entries that include a basic one.Consider the sequence of layersL11,L21,…,Ls-11,Ls1,Ls+11,…,Ln-11, and Ln1. Given below are possible arrangements of layers in this sequence. A basic layer Ls1 is denoted by 1; a nonbasic layer Ls1 is denoted by 0.Consider(1)
…11100111…; 1100111…; …1110011; 110011.(2)
…111010111…; 01111010…; …01011110; …001111010…; …010111100…; …0101111010….(3)
0111100…; …00111100…; …0011110.(4)
0111…; …1110; 10111…; …11101; 011110.We prove the first arrangement of item 1. Suppose that the two nonbasic layers are followed only by two basic layers, that is,…00110…. Let there be layers …Ls1, Ls+11, Ls+21, Ls+31, Ls+41….Consider layer pairsLs+12, Ls+13; Ls+12, Ls+23; Ls+22, Ls+13; Ls+22, and Ls+23.   At least one layer of each pair is basic. These four pairs of layers contain at least two basic entries, and these entries are located in layers Ls+21 and Ls+31. The pair Ls+32, Ls+33 includes a basic layer. The first coordinate of the basic layer entry may be s+2, s+3, or s+4. But the  Ls+21 and Ls+31 layers are occupied, while the Ls+41 layer is nonbasic. There is a contradiction.The other arrangements are proved in a similar way.Thus, nonbasic layers may not be arranged closer than those in the above variants. But these variants do not allow for the composition of a combination containing more than[n/3] nonbasic layers. Hence, it follows that if a trajectory includes more than [n/3] nonbasic entries, then one of the variants is violated and nonbasic trajectory entries can be replaced by a set of entries containing a basic entry.


## 3. Application to the Three-Dimensional Assignment Problem

The three-dimensional assignment problem (AP3) is an important combinatorial optimization problem. It is sufficient to note that the particular case of AP3, the 3-dimensional matching problem, is one of the six main NP-hard problems [7]. The formal AP3 statement is as follows: for a matrix ∥aijk∥∈Rn3, find permutations x,y∈Sn such that ∑i=1naix(i)y(i) is maximized.In this paper, the AP3 is considered for a special class ofn×n×n-matrices U(n). A matrix
(3)∥aijk∥∈U(n),ifaijk≥0,minaijk∈Gaijk≥C·maxaijk∈Haijk,C≥3.One of AP3 interpretations is the following. There aren employees and two job sets of n jobs each. If the ith employee performs the jth job of the first set and the kth job of the second set, then the effect equals aijk. It is required to distribute the jobs among the employees in such a way so as to maximize the total effect.Let us describe the situation that will lead to the AP3 for matrices fromU(n). As a rule, the employees are ordered by qualification, while the jobs are ordered by complexity. A higher effect is reached when a more qualified employee performs a more complex job, and we may arrive at the AP3 for matrices from U(n).The particular cases of AP3 [5, 8–11], the nonpolynomial exact algorithms for the AP3 [6, 12], and heuristics for the AP3 [13, 14] were considered.The NP-hard particular cases of the traveling salesman problem, with sets of matrices whose structures are similar to those of matrices fromU(n), have been considered previously [15, 16].Theorem 3.
The AP3 for matrices fromU(n) is NP-hard.Proof.
Let∥bijk∥∈Rn3, bijk≥0 and numbers A, B are such that A=3·maxbijk, B=nA.
Consider4n×4n×4n-matrix ∥aijk∥ with nonnegative entries
(4)a4s-3,4s-2,4s-2=Bs=1,…,n;a4s-2,4s-1,4s-1=Bs=1,…,n;a4s,4s,4s=Bs=1,…,n;aruv=Ar,u,v=1,…,n;if|r-u|≤1,|r-v|≤1,|u-v|≤1,aruv≠B;a4i-1,4j-3,4k-3=bijki,j,k=1,…,n;aijk=0in other cases.
The matrix∥aijk∥∈U(4n).
All entries that are equal toB belong to the optimal solution of AP3 for ∥aijk∥ matrix. This signifies that if the optimal solution of AP3 for ∥aijk∥ matrix is known, then the optimal solution of AP3 for ∥bijk∥ matrix is known as well. Therefore, the AP3 for arbitrary matrices is polynomially reducible to the AP3 for matrices from U(n).Corollary 4.
If∥aijk∥∈U(n), then a set T exists on which the AP3 optimum is reached and the number of T∩H set entries is no more than [n/3].
Indeed, if for optimalT of matrix ∥aijk∥∈U(n) the number of T∩H set entries is more than [n/3], then, according to Theorem 1, it is possible to make such replacement of entries such that the sum of  T set entries will not change and the number of T∩H set entries is reduced.Theorem 5.
If∥aijk∥∈U(n), then the AP3 optimum for a ∥aijk′∥ matrix, where aijk′=aijk for aijk′∈G and  aijk′=0 for aijk′∈H, represents an approximation for the AP3 optimum of the ∥aijk∥ matrix with a relative error not exceeding 1/(3C).Proof.
Let∥aijk∥∈U(n); m1 is the AP3 optimum for ∥aijk∥; f,g∈Sn are such that m1=∑i=1naif(i)g(i), and the number of {aif(i)g(i)∣i=1,…,n}∩H set entries is no more than [n/3]; m2 is the sum of {aif(i)g(i)∣i=1,…,n}∩H set entries and m3=m1-m2; m′ is the AP3 optimum for ∥aijk′∥.
Note thatm3=∑i=1naif(i)g(i)′ and m′≥m3.
Insofar asaijk≥aijk′,i,j,k=1,…,n, then m1≥m′. Hence, m3≤m′≤m1 and (m1-m′)/m1≤(m1-m3)/m1=m2/m1.
Sincem2≤(1/3)n·maxaijk∈Haijk and m1≥n·minaijk∈Gaijk, then m2/m1≤1/(3C). Hence, (m1-m′)/m1≤1/(3C), and the relative error of m′ taken as the AP3 approximate solution for the ∥aijk∥ matrix is no more than 1/(3C).Remark 6.
An exactO(n)-algorithm of AP3 solution has been constructed [9] for n×n×n-matrices ∥aijk∥ such that aijk≥0 for aijk∈G and aijk=0 for aijk∈H using dynamical programming.



---

*Source: 797249-2013-10-30.xml*