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

Question

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.

Answer 1

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.

Answer 2

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;

}

Answer 3

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.