Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
10  
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. –  Robin Chapman Sep 29 '10 at 9:02
3  
Just adding one small note - the result has rank either $0$ or $1$ since you have matrices of rank $1$ in the product. –  Moshe Schwartz Sep 29 '10 at 9:41
4  
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. –  Federico Poloni Sep 29 '10 at 12:20
1  
@ 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. –  Unknown Oct 1 '10 at 18:55
5  
I fixed up your math display. Like almost all other problems with math, this is caused by interference from the MarkDown software (it eats up the backslashes). And like almost all other problems with math display, you can solve it by enclosing the math environment inside backticks. –  Willie Wong Oct 1 '10 at 19:32
show 2 more comments

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
1  
Looking inside the book in Google Books, I see that it is satisfying to my needs. Thank you very much. –  Unknown Oct 2 '10 at 8:00
2  
So, you are Craig Citro? –  Unknown Oct 3 '10 at 17:58
add comment

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.

-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
$.................$

-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

\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.

share|improve this answer
    
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? –  Peter Shor Nov 21 '10 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)}$. –  Unknown Nov 21 '10 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. –  Unknown Nov 21 '10 at 13:25
add comment

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;

}

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.