# Some Nonexistence and Asymptotic Existence Results for Weighing Matrices

Authors: Ebrahim Ghaderpour
Journal: International Journal of Combinatorics
 (2016)

---

## Abstract

Orthogonal designs and weighing matrices have many applications in areas such as coding theory, cryptography, wireless networking, and communication. In this paper, we first show that if positive integerk cannot be written as the sum of three integer squares, then there does not exist any skew-symmetric weighing matrix of order 4n and weight k, where n is an odd positive integer. Then we show that, for any square k, there is an integer N(k) such that, for each n≥N(k), there is a symmetric weighing matrix of order n and weight k. Moreover, we improve some of the asymptotic existence results for weighing matrices obtained by Eades, Geramita, and Seberry.


---

## Body

## 1. Introduction

Anorthogonal design (OD) [1, Chapter 1] of order n and type (s1,…,sl), denoted as OD(n;s1,…,sl), is a square matrix X of order n with entries from {0,±x1,…,±xl}, where xj’s are commuting variables, that satisfies (1)XXT=∑j=1lsjxj2In,where XT is the transpose of X and In is the identity matrix of order n. An OD with no zero entry is called a full OD. Equating all variables to 1 in any full OD results in a Hadamard matrix. Equating all variables to 1 in any OD of order n results in a weighing matrix, denoted as W(n,k), where k is the weight that is the number of nonzero entries in each row (column) of the weighing matrix.TheKronecker product of two matrices A=[aij] and B of orders m×n and r×s, respectively, is denoted by A⊗B, and it is the matrix of order mr×ns defined by (2)A⊗B=a11Ba12B⋯a1nBa21Ba22B⋯a2nB⋮⋮⋮am1Bam2B⋯amnB. Thedirect sum of A and B is denoted by A⊕B, and it is the matrix of order (m+r)×(n+s) which is defined as follows: (3)A⊕B=A00B, where 0 represents a zero matrix of appropriate dimension.LetA=(a1,…,an) and D=(d1,…,dn), where ai’s and bi’s belong to a commutative ring (e.g., R). Square matrix C=[cij] of order n is calledcirculant if cij=aj-i+1, where j-i is reduced modulo n. Square matrix B=[bij] of order n is calledback-circulant if bij=di+j-1, where i+j-2 is reduced modulo n. We have BCT=CBT and B=BT; that is, any back-circulant matrix is symmetric. Let R=[rij] be a square matrix of order n, where rij=1 if i+j=1 modulo n and rij=0 otherwise. Matrix R is calledback-diagonal matrix. It is not hard to see that matrix CR is back-circulant and so symmetric (cf. [1, Chapter 4]).Arational family of order n and type (s1,…,sk), where si’s are positive rational numbers, is a collection of k rational matrices of order n, A1,…,Ak, that satisfy AiAiT=siIn (1≤i≤k) and AiAjT=-AjAiT, (1≤i≠j≤k). A is a skew-symmetric matrix if AT=-A. Two matrices of the same dimension aredisjoint if their entrywise multiplication is a zero matrix [1, Chapters 1, 2].Geramita and Seberry [1, Chapter 7] showed some existence results for weighing matrices. They showed that when the orders of ODs and weighing matrices aremuch larger than the number of nonzero entries in each row, the necessary conditions for existence of ODs and weighing matrices are also sufficient. In this paper, we show some nonexistence results on weighing matrices and some asymptotic results for existence of weighing matrices.


## 2. Nonexistence Results for Weighing Matrices

In this section, we show some nonexistence results for weighing matrices. The results are summarized in Theorems4 and 5 (known) and Theorem 10.Lemma 1 (e.g., [2, Chapter 2]).
The eigenvalues of a symmetric matrix with real entries are real.Lemma 2 (e.g., [2, Chapter 2]).
The eigenvalues of a skew-symmetric matrix with real entries are of the form±ib, where b is a real number.Lemma 3 (e.g., [1]).
The absolute values of the eigenvalues of a weighing matrixW(n,k) are k.Theorem 4 (e.g., [3]).
There does not exist any symmetric weighing matrix with zero diagonal of odd order.Proof.
Suppose thatW=W(n,k),n odd, is a symmetric weighing matrix with zero diagonal. From Linear Algebra, tr(W)=∑t=1n‍λt, where λt’s are eigenvalues of W. By Lemmas 1 and 3, since λt=±k,(4)trW=∑t=1nλt=ck.Since n is odd, c must be odd and therefore nonzero, but, by assumption, tr(W)=0, which is a contradiction.Theorem 5 (e.g., [3]).
There is no skew-symmetric weighing matrix of odd order.Proof.
Assume thatW=W(n,k) is a skew-symmetric weighing matrix of odd order. From Lemmas 2 and 3, eigenvalues of W are in form ±ik. Therefore, (5)trW=∑t=1nλt=cik. Since n is odd, c must be odd and so nonzero, but since W is a skew-symmetric matrix, tr(W)=0 which is a contradiction.Next, we show that ifn is any odd number and k cannot be written as the sum of three integer squares, then there is no skew-symmetric weighing matrix W(4n,k). To do so, we first bring the following well known results.Lemma 6 (e.g., [4]).
A positive integer can be written as the sum of three integer squares if and only if it is not of the form4l(8k+7), where l,k≥0.The following lemma is a useful result that can be concluded from Lemma6, and, for the sake of completion, we bring its proof.Lemma 7 (e.g., [4]).
A positive integer is the sum of three rational squares if and only if it is the sum of three integer squares.Proof.
Suppose that a positive integern is the sum of three rational squares. Reducing the three rational numbers to the same denominator, one may write (6)m2n=α2+β2+γ2,where α,β, and γ are integers. Suppose that n cannot be written as the sum of three integer squares. From Lemma 6, there exist nonnegative integers k,l such that n=4l(8k+7). One may write m as 2r(2s+1), for some nonnegative integers r,s. Thus, m2=4r(4(s2+s)+1)=4r(8b+1), where b=(s2+s)/2 is a nonnegative integer, and so (7)m2n=4r+l8k+78b+1=4r+l8c+7,where c=8kb+k+7b. This is a contradiction because, by Lemma 6, m2n cannot be written as the sum of three integer squares, whereas by assumption m2n=α2+β2+γ2. Therefore, the result follows.Lemma 8 (Shapiro [5]).
There is a rational family in ordern=2mt, t odd, of type (s1,…,sk) if and only if there is a rational family of the same type in order 2m.Lemma 9 (Geramita and Seberry [1]).
A necessary and sufficient condition that there is a rational family of type[1,k] in order 4 is that k is a sum of three rational squares.Proof.
Suppose that{A,B} is a rational family of type [1,k] in order 4. Then {I=ATA,D=ATB} is also a rational family of the same type and order. Thus D=-DT and DDT=kI. Since D is a skew-symmetric matrix, the diagonal of D is zero, so k is a sum of three rational squares.
Now letk=a2+b2+c2, where a,b, and c are rational numbers. If we let (8)D=0abc-a0-cb-bc0-a-c-ba0,then {I,D} is a rational family of type [1,k] and order 4.We use Lemmas7, 8, and 9 to prove the following nonexistence result.Theorem 10.
Suppose that positive integerk cannot be written as the sum of three integer squares. Then there does not exist skew-symmetric W(4n,k), for any odd number n.Proof.
If there is skew-symmetricW=W(4n,k) for some odd number n, then {I4n,W} is a rational family of type [1,k] and order 4n. Thus, by Lemma 8, there is a rational family of type [1,k] and order 4. Lemmas 7 and 9 imply that k must be the sum of three integer squares.


## 3. Asymptotic Existence Results of Weighing Matrices

In this section, we provide some asymptotic results for existence of weighing matrices. These results are summarized in Theorem21 and Theorems 22 and 25 (for ODs) that use different methodologies to improve the known results shown by Geramita and Seberry [1, Chapter 7].Lemma 11 (e.g., [1]).
A necessary and sufficient condition that there existsOD(n;u1,…,uk) is that there exists a family {A1,…,Ak} of pairwise disjoint square matrices of order n with entries from {0,±1} satisfying(i)
Ai is a W(n,ui),1≤i≤k,(ii)
AiAjT=-AjAiT,1≤i≠j≤k.The following lemma, due to Sylvester, is known, and we bring its proof.Lemma 12 (see [6]).
Letx and y be two relatively prime positive integers. Then every integer N≥xy can be written in the form ax+by, where a and b are nonnegative integers.Proof.
LetN be an integer greater than or equal to xy. Since x and y are relatively prime, there are integers c and d such that cx+dy=N (see [4]). So, (9)c+jyx+d-jxy=N,where j∈Z. One can choose j such that 0≤c+jy≤y-1. For such j, we let a=c+jy and b=d-jx. The condition N≥xy implies that b must be positive.The following lemma shows how to construct ODs of higher orders by using two ODs of the same types but different orders. The first part of the lemma is known (cf. [1, Lemma 7.22]).Lemma 13.
Suppose that there areA=OD(n1;u1,…,um) and B=OD(n2;u1,…,um). Let h=gcd(n1,n2). Then there is an integer N such that, for each t≥N, there is OD(ht;u1,…,um). Moreover, if A and B are symmetric, then there is an integer N such that, for each t≥N, there is symmetric OD(ht;u1,…,um).Proof.
Letx=n1/h and y=n2/h. Then x and y are relatively prime. Let N=xy, and let t be a positive integer ≥N. By Lemma 12, there are nonnegative integers a and b such that t=ax+by. Since there exist OD(n1;u1,…,um) and OD(n2;u1,…,um), there are families {A1,…,Am} of order n1 and {B1,…,Bm} of order n2 satisfying the conditions in Lemma 11. We define the family (10)S=Ia⊗A1⊕Ib⊗B1,…,Ia⊗Am⊕Ib⊗Bmof order an1+bn2=ht. It can be seen that this family satisfies the conditions of Lemma 11; therefore it makes OD(ht;u1,…,um).
Now ifA and B are symmetric, then Ai’s and Bi’s, 1≤i≤m, are all symmetric. Since (11)A⊗B⊕C⊗DT=AT⊗BT⊕CT⊗DT,set S consists of m symmetric matrices of order ht satisfying the conditions of Lemma 11, and so they generate symmetric OD(ht;u1,…,um).Theorem 14 (Wallis and Whiteman [7]).
Letq be a prime power. Then there is circulant W(q2+q+1,q2).Corollary 15 (see [1, 8]).
Suppose thatq is a prime power and c is any positive integer. Then there is circulant W(c(q2+q+1),q2).Proof.
Letc be a fixed positive integer. From Theorem 14, we know that there exists a circulant W(q2+q+1,q2). Suppose that the first row of this matrix is (a1,a2,…,aq2+q+1). Let (12)ϕx=∑i=1q2+q+1aixi.Thus, ϕ(ξ)ϕ(ξ-1)=q2, where ξ is a primitive root of unity and ξq2+q+1=1. For 1≤j≤c(q2+q+1) define (13)bj≔aj/cj≡1mod⁡c0otherwise, where x is the smallest integer greater than or equal to x. We show that if W=circ(b1,b2,…,bc(q2+q+1)), then W is W(c(q2+q+1),q2). To see this, let (14)ψy=∑j=1cq2+q+1bjyj. Thus we have (15)ψy=∑i=1q2+q+1aiyci-1+1=y1-c∑i=1q2+q+1aiyci.Since ϕ(ξ)ϕ(ξ-1)=q2, for all ξ such that ξq2+q+1=1,ψ(ξ)ψ(ξ-1)=q2, for all ξ such that ξq2+q+1=1. Applying the finite Parseval relation (16)∑i=1cq2+q+1bibi+r=1cq2+q+1∑j=1cq2+q+1ψξj2ξjr,where i+r-1 is reduced modulo c(q2+q+1), for r=0 gives (17)∑i=1cq2+q+1bi2=1cq2+q+1cq2+q+1q2=q2.And, for 1≤r≤c(q2+q+1)-1, ∑i=1c(q2+q+1)‍bibi+r=0. Therefore, W is circulant W(c(q2+q+1),q2).The next lemma shows how to make a symmetric OD to be used for Theorem21.Lemma 16.
Letk be a positive integer. Then there exists symmetric OD(2k;1(k)).Proof.
DefineA1=⨂m=1kP and, for 2≤n≤k, An=⨂m=1n-2I⊗Q⨂m=nkP, where (18)P=0110,Q=100-1,I=1001.It can be directly verified that the family {A1,…,Ak} of order 2k satisfies the conditions of Lemma 11, and therefore it makes symmetric OD(2k;1(k)). Note that P,Q, and I are symmetric.Theorem 17 (Robinson [9]).
AllOD(2t;1,1,a,b,c) exist, where t≥3 and a+b+c=2t-2.We prove the following well known lemma by giving a proof which is different from the proof in [1, Lemma 7.27].Lemma 18.
For any sequence(k1,k2,k3,k4) of positive integers, there is a positive integer d such that there is skew-symmetric OD(2d;k1,k2,k3,k4).Proof.
Lett1 and t2 be the smallest positive integers such that 1+k1+k2≤2t1 and 1+k3+k4≤2t2. By Theorem 17, there are A=OD(2t1;1,k1,k2) and B=OD(2t2;1,k3,k4). Without loss of generality, assume that {I2t1,A1,A2} and {I2t2,B1,B2} are two families corresponding to A and B satisfying the conditions of Lemma 11. Let P and Q be the same matrices as in the proof of Lemma 16. It can be directly verified that the family (19)I2t2⊗A1⊗P,I2t2⊗A2⊗P,B1⊗I2t1⊗Q,B2⊗I2t1⊗Qof four skew-symmetric matrices satisfies all conditions of Lemma 11, and so it makes skew-symmetric OD(2t1+t2+1;k1,k2,k3,k4).Corollary 19 (see [1]).
Given any sequence(k1,k2,k3,k4) of positive integers, there exists a positive integer d such that there is OD(2d;1,k1,k2,k3,k4).The following theorem, due to Geramita and Seberry, is known.Theorem 20 (Geramita and Seberry [1, Theorem 7.14]).
Suppose thatk is a square. Then there is an integer N=N(k) such that, for each n≥N, there is W(n,k).We use a slightly different method to the proof of Theorem20 to give a proof of the following improved result.Theorem 21.
Suppose thatk is a square. Then there is an integer N=N(k) such that, for each n≥N, there is symmetric W(n,k).Proof.
Assume thatk=∏i=1m‍qi2, where qi is either 1 or a prime power. By Theorem 14, for each i there exists circulant Wi=W(qi2+qi+1,qi2). Let (20)W=⨂i=1m⁡WiRi,where Ri is the back-diagonal matrix of order qi2+qi+1. It can be seen that W is symmetric W∏i=1m‍(qi2+qi+1),∏i=1m‍qi2.
Thus, there is an odd numbert=∏i=1m‍(qi2+qi+1) such that there is symmetric W(t,k). Moreover, from Lemma 16, there exists symmetric OD(2k;1(k)), and so there is symmetric W(2k,k). Now since t is odd, gcd(2k,t)=1. Lemma 13 implies that there is a positive integer N=N(k) such that, for each n≥N, there exists symmetric W(n,k).We prove the following theorem by a slightly different method to the proof that first was given by Eades [1, 8].Theorem 22.
Suppose thatk=k12+k22, where k1 and k2 are two nonzero integers. Then there is an integer N=N(k) such that, for each n≥N, there is OD(2n;k12,k22).Proof.
Forj=1,2, let kj2=∏i=1m‍qij2, where qij is either 1 or a prime power. For each i, 1≤i≤m, let bi=lcm{qi12+qi1+1,qi22+qi2+1}. From Corollary 15, for each j, j=1,2, and each i, 1≤i≤m, there exists circulant Wij=W(bi,qij2). It can be seen that the following 2q×2q matrix is OD(2q;k12,k22),(21)x⨂i=1m⁡Wi1Riy⨂i=1m⁡Wi2y⨂i=1m⁡Wi2-x⨂i=1m⁡Wi1Ri, where Ri is the back-diagonal matrix of order bi and q=∏i=1m‍bi is an odd number. From Theorem 17, one can choose the smallest positive integer k such that there is OD(2k;k12,k22). Since gcd(2q,2k)=2, Lemma 13 implies that there is an integer N=N(k) such that, for each n≥N, there is OD(2n;k12,k22).Using the methodology in the proof of Theorem22, the asymptotic bounds for the following two corollaries given by Eades [8] are improved.Corollary 23.
Suppose thatk is the sum of two nonzero integer squares. Then there is an integer N=N(k) such that, for each n≥N, there is W(2n,k).Proof.
Letk=k12+k22, where k1 and k2 are integers. From Theorem 22, there is an integer N=N(k) such that, for any n≥N, there is OD(2n;k12,k22), and so there is W(2n,k).Corollary 24.
Suppose thatd is an integer square. Then there exists an integer N=N(d) such that, for each n≥N, there is skew-symmetric W(2n,d).Proof.
Suppose thatd=a2. Let k1=1 and k2=a. By Theorem 22, there exists an integer N=N(d) such that, for each n≥N, there is OD(2n;1,d), and so there is skew-symmetric W(2n,d).We now use a different method to show Theorem25 shown by Eades [1, 8] to improve the bounds (N) for the asymptotic existence of ODs of order 4n, and consequently we prove Corollaries 26, 27, and 28.Theorem 25.
Suppose thatk=k12+k22+k32+k42, where k1,k2,k3, and k4 are nonzero integers. Then there is an integer N=N(k) such that, for each n≥N, there is OD(4n;k12,k22,k32,k42).Proof.
Assume thatk=k12+k22+k32+k42 and k1,k2,k3, and k4 are nonzero integers. Let kj2=∏i=1m‍qij2, where qij is either 1 or a prime power. For each i, 1≤i≤m, let bi=lcm{qij2+qij+1;j=1,2,3,4}. From Corollary 15, for each j, 1≤j≤4, and each i, 1≤i≤m, there exists circulant Wij=W(bi,qij2). Putting (22)A=⨂i=1m⁡Wi1Ri,B=⨂i=1m⁡Wi2,C=⨂i=1m⁡Wi3,D=⨂i=1m⁡Wi4,in the following array (Goethals and Seidel [10]) gives OD(4q;k12,k22,k32,k42): (23)xAyBzCuD-yBxAuDT-zCT-zC-uDTxAyBT-uDzCT-yBTxA, where q=∏i=1m‍bi which is an odd number and Ri is the back-diagonal matrix of order bi.
By Lemma18, there is OD(2d;k12,k22,k32,k42) for some suitable integer d≥2. Since, for d≥2, gcd(4q,2d)=4, Lemma 13 implies that there is an integer N=N(k) such that, for each n≥N, there is OD(4n;k12,k22,k32,k42). Note that if some of ki’s are zero, then we consider the zero matrices.Corollary 26.
Suppose thatd is any positive integer. Then there is an integer N=N(d) such that, for each n≥N, there is W(4n,d).Proof.
It is a well known theorem of Lagrange [11] that every positive integer can be written in the sum of four integer squares. Let d=k12+k22+k32+k42. From Theorem 25, there is an integer N=N(k) such that, for each n≥N, there is OD(4n;k12,k22,k32,k42), and therefore there is W(4n,d).Corollary 27.
Suppose thatd is the sum of three integer squares. Then there exists an integer N=N(d) such that, for each n≥N, there is skew-symmetric W(4n,d).Proof.
Considerd=a2+b2+c2, for some integers a,b, and c. Substituting k1=a, k2=b, k3=c, and k4=1 in Theorem 25 gives the result. Note that the existence of OD(n;1,h) is equivalent to existence of skew-symmetric W(n,h).Corollary 28.
Suppose thatd is any positive integer. Then there exists an integer N=N(d) such that, for each n≥N, there is skew-symmetric W(8n,d).Proof.
By Lagrange’s theorem [12], one can write d=k12+k22+k32+k42, where ki’s are nonnegative integers. Let A,B,C, and D be the same matrices as in Theorem 25. It can be seen that the following matrix gives OD(8q;1,k12,k22,k32,k42), where q is obtained as in Theorem 25, and is an odd number: (24)
x
A
y
B
z
C
u
D
w
I
q
0
0
0
-
y
B
x
A
u
D
T
-
z
C
T
0
w
I
q
0
0
-
z
C
-
u
D
T
x
A
y
B
T
0
0
w
I
q
0
-
u
D
z
C
T
-
y
B
T
x
A
0
0
0
w
I
q
w
I
q
0
0
0
-
x
A
y
B
T
z
C
T
u
D
T
0
w
I
q
0
0
-
y
B
T
-
x
A
u
D
-
z
C
0
0
w
I
q
0
-
z
C
T
-
u
D
-
x
A
y
B
0
0
0
w
I
q
-
u
D
T
z
C
-
y
B
-
x
A
. From Corollary 19, there is OD(2d;1,k12,k22,k32,k42) for some suitable integer d≥3. Since, for d≥3, gcd(8q,2d)=8, Lemma 13 implies that there is an integer N=N(d) such that, for any n≥N, there is OD(8n;1,k12,k22,k32,k42), and so there is skew-symmetric W(8n,d).Example 29.
Suppose thatk=92. Let k1=2,k2=4,k3=6, and k4=6 in Theorem 25. Also, let q11=2,q21=1,q12=4,q22=1,q13=2,q23=3,q14=2, and q24=3. Then b1=lcm{7,21,7,7}=21, and b2=lcm{3,3,13,13}=39. By Theorem 25, there is (25)OD4·21·39;22,42,62,62.From Lemma 18, there is OD(213;22,42,62,62). By Lemma 13, since h=gcd(4·21·39,213)=4, we have N(92)≤211·32·7·13, and so, for each n≥N(92), there are W(4n,92) and skew-symmetric W(8n,92).



---

*Source: 2162849-2016-03-13.xml*