# 'Sign matrices'-(-1,+1) square matrices

My question arises from a discussion on an answer given by Maurizio Monge here.I do not know if there is a known terminology for such matrices. By "sign matrices," I mean square matrices whose entries are in ${-1,+1}$.

For instance, $\begin{bmatrix} 1 &-1 \\ -1& -1 \end{bmatrix}$ , $\begin{bmatrix} -1&1&1 \\ 1&1&-1 \\ -1&-1&-1 \end{bmatrix}$

Clearly, there are $2^{n^2}$ sign matrices of size $n\times n$. So, we start their theory by enumerating them as follows. For a matrix of size $n\times n$ we consider a truth table of $n^2$ arguments and therefore $2^{n^2}$ rows. Each row corresponds to the entries in one matrix$(a_{11},a_{12},\dots,a_{1n},a_{21},a_{22},\dots,a_{nn})$. Let $M_{(n,k)}$ be the $n \times n$ sign matrix corresponding to the $k^th$ row of the truth table.

Question: Does the following matrix product give the zero matrix for sign matrices of even size?

$\prod_{k=1}^{2^{n^2}}M_{(n,k)}$

Thank you. As usual, I will be delighted if you point me to good references on this.

• The product notation $\prod_{n=1}^{2^{n^2}}$ is rather treacherous when dealing with a noncommutative ring. There are orderings of your $M_{(n,k)}$ having two consecutive matrices which multiply to zero. Sep 29, 2010 at 9:02
• Just adding one small note - the result has rank either $0$ or $1$ since you have matrices of rank $1$ in the product. Sep 29, 2010 at 9:41
• It is only tangentially related to what you're asking, but there is a wide literature on the so-called sign pattern matrices, that is, matrices with entries in the set of three symbols $\{-,0,+\}$. They are meant to model applications in which only the sign of the entries of a matrix is known; in some cases, this is sufficient to deduce (non)singularity, rank, or irreducibility properties. A good starting point is chapter 33 in Handbook of Linear Algebra by Hogben. Sep 29, 2010 at 12:20
• @ Robin. Thanks .You are right. I use the product for the sake of notation and the factors are multiplied in the order they appear, so no commutation. @Moshe, thanks. @Federico, that's what I am looking for, thank you very much. So, when coming to deducing (non)singularity, what specific theorem is there? I think the answer will greatly aid the path to the solution of my question. Oct 1, 2010 at 18:55

Much is known about sign nonsingular patterns (sign patterns for which nonsingularity does not depend on the numerical values), if I remember correctly there is a characterization. Less is known about sign patterns which have allow (but do not require) nonsingularity. I suggest looking at the book Matrices of sign-solvable linear systems by Brualdi and Shader.

• Looking inside the book in Google Books, I see that it is satisfying to my needs. Thank you very much. Oct 2, 2010 at 8:00
• So, you are Craig Citro? Oct 3, 2010 at 17:58

Here is the $C$++ code that my compiler cannot process as the array size is 'too large'. I tried some online compilers and still I cannot get the product. I occasionally think about this problem on weekends. O dear, it is tormenting me.

#include<iostream.h>
#include<math.h>
int main()
int main()
{
/* Constructing the auxiliary table for enumerating the sign matrices*/
int Table[65536][16];
int k, j, i;
for (k = 0; k < 16; k++)                 // number of columns
{
for (j = 0; j < pow(2,(k + 1)); j++)    // number of times sign alternates  in  a column
{
for (i = 0; i < 65536; i++)     // number of rows
{
if (i >= pow(2,(16-k-1))*j && i < ( pow(2,(16-k-1))*(j + 1)) )
Table[i][k] = pow(-1,j);
}
}
}


/* Displaying the table*/ /*N.B. Except for checking some rows, it is unwise to print the table as there are 65536 rows.*/

  for (i = 0; i < 65536; i++)
{
for (k = 0; k < 16; k++)
{
cout << Table[i][k] << "  ";
}
cout << endl;
}


/Computing $M_4$/

//Entering the first sign matrix $M_{(4,1)}$

long double a = Table[0][0], b = Table[0][0], c = Table[0][0], d = Table[0][0],

e = Table[0][0], f = Table[0][0], g = Table[0][0], h = Table[0][0],

l = Table[0][0], m = Table[0][0], n = Table[0][0], o = Table[0][0],

p = Table[0][0], q = Table[0][0], r = Table[0][0], s = Table[0][0];

long double a1, b1, c1, d1, e1, f1, g1, h1, l1, m1, n1, o1, p1, q1, r1, s1;


/*Formula for multiplying the matrices in the prescribed order*/

for (i = 1; i < 65536; i++)       // i starts from 1 since the first row has already been entered

{

a1 = a * Table[i][0] + b * Table[i][4] + c * Table[i][8]  + d * Table[i][12];

b1 = a * Table[i][1] + b * Table[i][5] + c * Table[i][9]  + d * Table[i][13];

c1 = a * Table[i][2] + b * Table[i][6] + c * Table[i][10] + d * Table[i][14];

d1 = a * Table[i][3] + b * Table[i][7] + c * Table[i][11] + d * Table[i][15];

e1 = e * Table[i][0] + f * Table[i][4] + g * Table[i][8]  + h * Table[i][12];

f1 = e * Table[i][1] + f * Table[i][5] + g * Table[i][9]  + h * Table[i][13];

g1 = e * Table[i][2] + f * Table[i][6] + g * Table[i][10] + h * Table[i][14];

h1 = e * Table[i][3] + f * Table[i][7] + g * Table[i][11] + h * Table[i][15];

l1 = l * Table[i][0] + m * Table[i][4] + n * Table[i][8]  + o * Table[i][12];

m1 = l * Table[i][1] + m * Table[i][5] + n * Table[i][9]  + o * Table[i][13];

n1 = l * Table[i][2] + m * Table[i][6] + n * Table[i][10] + o * Table[i][14];

o1 = l * Table[i][3] + m * Table[i][7] + n * Table[i][11] + o * Table[i][15];

p1 = p * Table[i][0] + q * Table[i][4] + r * Table[i][8]  + s * Table[i][12];

q1 = p * Table[i][1] + q * Table[i][5] + r * Table[i][9]  + s * Table[i][13];

r1 = p * Table[i][2] + q * Table[i][6] + r * Table[i][10] + s * Table[i][14];

s1 = p * Table[i][3] + q * Table[i][7] + r * Table[i][11] + s * Table[i][15];

a = a1, b = b1, c = c1, d = d1, e = e1, f = f1, g = g1, h = h1, l =  l1,

m = m1, n = n1, o = o1, p = p1, q = q1, r = r1, s = s1;

}


/* Displaying the final product, i.e. $M_4$*/

cout << endl << endl;

cout << "\t\t"    << a << "\t" << b << "\t" << c << "\t" << d << "\t" << endl;

cout << "M_4 =\t" << e << "\t" << f << "\t" << g << "\t" << h << "\t" << endl;

cout << "\t\t"    << l << "\t" << m << "\t" << n << "\t" << o << "\t" << endl;

cout << "\t\t"    << p << "\t" << q << "\t" << r << "\t" << s << "\t" << endl;


return 0;

}

It is not part of the question but I consider it useful to give the result for the $M_3$ case( which I found using a $C$++ program). There are 512 rows and the matrix below is $M_3$. However, I am not completely certain since the compiler I used might have rounded off the numbers while multiplying the matrices though the data type used was long double,the most precise by far.

\begin{matrix} -1 & 1 & -1 & 1 & -1 & -1 & -1 & -1 & 1\\ -1 & 1 & -1 & 1 & -1 & -1 & -1 & -1 & -1\\ -1 & 1 & -1 & -1 & 1 & 1 & 1 & 1 & 1\\ -1 & 1 & -1 & -1 & 1 & 1 & 1 & 1 & -1\\ -1 & 1 & -1 & -1 & 1 & 1 & 1 & -1 & 1\\ -1 & 1 & -1 & -1 & 1 & 1 & 1 & -1 & -1\\ \end{matrix}

$$\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots$$

\begin{matrix} -1 & -1 & -1 & -1 & -1 & -1 & -1 & 1 & -1\\ -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & 1\\ -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 \end{matrix}

\begin{bmatrix} 1.50197\times10^{100} & 1.50197\times10^{100} & 1.50197\times10^{100}\\ 1.50197\times10^{100} & 1.50197\times10^{100} &1.50197\times10^{100} \\ 1.50197\times10^{100}& 1.50197\times10^{100} &1.50197\times10^{100} \end{bmatrix}

It is sad that the "array size" blows out of the compiler's capacity when running my program for the $M_4$ case, the case that would either kill or save my question.

• The result of a matrix product depends on the order of the matrices, so there should be ways of ordering this matrix product so the answer is not zero, and there are certainly ways of ordering this matrix product so the answer is zero. Did you have any particular ordering in mind? Nov 21, 2010 at 13:01
• Thanks for your comments. I use the product notation just for the sake of notation and the factors are multiplied in the order they appear, i.e. $M_{(3,1)} \times M_{(3,2)} \ldots M_{(2^{n^2},1)}$. Nov 21, 2010 at 13:15
• One way to get around the problem theoretically could be to decompose a given even matrix into $2 \times 2$ matrix blocks so that upon multiplication we will have all entries expressed in the form of a sum of product of $2 \times 2$ sign matrices. Since $M_2$ has been shown to be the zero matrix, maybe this approach will help to solve the problem. Nov 21, 2010 at 13:25