This is a follow-up quesiton to 
http://answers.google.com/answers/main?cmd=threadview&id=95946

I have another matrix that I want to represent in the same form as 
in the previous question (I have only two matrices that I'm concerned 
about, so I won't post further questions of this type).  The matrix is  

B=   1     0     0     1     0     0     0     0
     0     0     0     0     0     0     0     0
     0     0     0     0     1     0     0     1
     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0
     1     0     0     1     0     0     0     0
     0     0     0     0     0     0     0     0
     0     0     0     0     1     0     0     1

and the question is the same: how many Kronecker products of the 
form kron(X,kron(Y,Z)) with 2x2 matrices one needs to add to produce B: 

B = kron(X_1,kron(Y_1,Z_1)) +  kron(X_2,kron(Y_2,Z_2)) + ...   (1) 

B is a permutation of A from the previous question.  One of the ways to 
write it (other representations are possible, because the matrices 
have several zero rows/columns) is: 

B=P1*A*P2

where 

P1=[1 0 0 0 0 0 0 0; 
    0 0 1 0 0 0 0 0; 
    0 1 0 0 0 0 0 0; 
    0 0 0 1 0 0 0 0; 
    0 0 0 0 1 0 0 0; 
    0 0 0 0 0 0 1 0; 
    0 0 0 0 0 1 0 0; 
    0 0 0 0 0 0 0 1]; 

P2=[1 0 0 0 0 0 0 0; 
    0 0 0 0 1 0 0 0; 
    0 0 1 0 0 0 0 0; 
    0 0 0 0 0 0 1 0; 
    0 1 0 0 0 0 0 0; 
    0 0 0 0 0 1 0 0; 
    0 0 0 1 0 0 0 0; 
    0 0 0 0 0 0 0 1]; 

I thought it will be trivial to go from the solution for A to a permutation 
of A, but I just don't see how to do it.  

Again, the question is the same as in question 
http://answers.google.com/answers/main?cmd=threadview&id=95946 : 
minimize the number of terms in (1) using any 2x2 matrices X_i, Y_i, and Z_i.  
Representation with 8 terms is trivial and suboptimal.  OPTIMIAL solution 
that minimizes the number of terms is sought with the PROOF OPTIMALITY.  
A computational proof (Matlab, C/C++, or Fortran prefered) is okay if the code 
is included with the answer. 

Thanks.

---

Request for Question Clarification by mathtalk-ga on 29 Nov 2002 18:36 PST

Hi, ilya-ga:

I'm posting this request for clarification to determine your current
level of interest in this problem.

As you probably recall, in the comments below I "conjecture" that any
8x8 real matrix could be expressed as a sum of seven of the given real
triple Kronecker products, and that almost all 8x8 real matrices
cannot be expressed as a sum of six or fewer of the such terms.

I did some numerical computations and was able to (numerically)
express your specific matrix as a sum of seven of these triple 2x2
products using my favorite tool for inexpensive optimization projects
(Excel with the Solver add-in).  The task of approximating the same
matrix using only six terms "fails" numerically, with the suggestive
result of Frobenius norm 1 (roughly) in the error of approximation
(sum of squares of matrix entries).

I thought this might be worth mentioning since you had originally
expressed interest in a computational proof, and since the answer
(tensor rank 7) may be different from what you originally anticipated.

regards, mathtalk-ga

---

Clarification of Question by ilya-ga on 02 Dec 2002 23:54 PST

Dear mathtalk-ga, 

Thank you for your comments.  I also came up with a seven-term solution 
and suspected that it cannot be improved, although I couldn't prove it 
either analytically or numerically.  Unfortunately, I don't have Ecxel 
to reproduce your experiments, and for the numerical solution I was hoping 
to get the code I could play with - anything but Excel probably would have 
worked :( 

I don't know if I should accept your answer.  On the one hand I didn't 
rule out Excel stating the question, but on the other hand, even if you 
post you code, the Excel proof doesn't help me much.  Please let me konw 
what you think. 

Thanks.

It seems clear that a permutation of the matrix might require more or
fewer terms as a sum of the Kronecker products.

It seems to me that this similarity permutation:

1 1 0 0 0 0 0 0 
1 1 0 0 0 0 0 0 
0 0 1 1 0 0 0 0
0 0 1 1 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 

is just a single Kronecker product, while you have (in the other
question) an example requiring the sum of four Kronecker products to
express.

regards, mathtalk-ga

Sorry, I left off a couple of zero rows in the matrix.  Hope the
meaning is clear...

-- mathtalk-ga

mathtalk-ga is correct. This matrix is trickier to handle than the other matrix.

Hi ilya:

I tried my Maple computations for this matrix as well. As before, the
calculation for the 1- through 3-term versions showed no solutions,
while the 4-term version ran "forever".

I've also banged it around in my head, and can't come up with any
solution better than the obvious 8-term one.

websearcher-ga

websearcher-ga: don't you have to check it with 7 terms, not 4?

I agree it "clearly" requires 8 terms; and I am sure there is a simple
proof of this (poincare-ga , where are you?) but I sure can't see one.

By the way is your maple code running in C or R ? There could be a
solution in C but not in R .

rbnn:

I wasn't suggesting that my checking the 4-term sum was any sort of
"proof" that it takes 8-terms - was just adding extra (computational)
information to the discussion.

Seeing as the calculation times are increasing exponentially, there's
no way I'd be able to check a 7-term solution. :-)

Maple is it's own interpretive language - though much of the
underlying library is written in C.

websearcher-ga

Hi,

Sorry for my vagueness - I meant, when Maple checks the entries, is it
doing computations over the field of complex numbers, C, over the
field of reals, R.

Hi rbnn:

C.    :-)

websearcher-ga

I know some great mathematicians; I'd be willing to run the problem by
them if the price went up a lot. I really shouldn't spend more time on
it myself but it's such a pretty problem I'm sure I will (however, I'm
far from a great mathematician and I'm skeptical I'll figure out a
solution)

Here's a "degrees of freedom" calculation, which doesn't prove
anything about the specific matrix given here, but is very suggestive.

The "generic" 8x8 matrix lives in a vector space of dimension 64.  We
are asked to express a particular such matrix as a sum (linear
combination) of Kronecker products involving three 2x2 matrices, using
the minimum number of such products.

Now the (concatenated) Kronecker product of three 2x2 matrices has ten
independent parameters (due to the bilinearity of the Kronecker
product).

This shows that some 8x8 matrices cannot be expressed as the sum of
six or fewer such Kronecker products, and suggests that the generic
case might well be expressed (non-uniquely) as a sum of seven or fewer
Kronecker products.

regards, mathtalk-ga

mathtalk-ga: what do you mean by "the concatenated product of 3 2x2
matrices has 10 independent parameters"?

rbnn-ga: I guess what mathtalk-ga means by "the concatenated product of 3 2x2 
matrices has 10 independent parameters" is that in an expression 
kron(X,kron(Y,Z)) you can normalize two of the matrices, by say setting 
X(1,1)=Y(1,1)=1 , and still cover the space of the resulting matrices by 
varying the remaining 10 free parameters. (Acutally it's probably better 
to set some norm of two matrices to 1, so we don't have to worry about 
corner cases when some entries are 0). 

A comment to mathtalk-ga: yes, with 10 variables in each concatenated 
Kronecker product, some 8x8 matrices will require at least seven terms.  
But, as you pointed out, it's not clear that it works the other way 
(any matrix can be represented with 7 products).  It's not a linear space, 
so just counting the dimensions won't do it.  Besides, we are talking about 
a particular, fairly simple matrix, not a general case. 

Thanks.

ilya-ga: I am unable to prove the correctness of your statement "some
8x8 matrices will require at least seven terms". I believe it, of
course; I just can't prove it. Want to reverse roles and explain :-) ?

Hi, rbnn-ga:

To give a short but "big hammer" answer to your question, it follows
from thinking of the mapping from (say) sums of six tensors into the
8x8 matrices as a differentiable mapping of differentiable manifolds.

The dimension of the "domain" here are the six times ten (60)
parameters or degrees of freedom available in the sum.  This could not
possibly "fill" the 64 dimensional space of the 8x8 matrices.  Some
(most) 8x8 matrices cannot be expressed as a sum of six of the 2x2x2
tensor products considered here.

regards, mathtalk-ga

I understand now; thanks mathtalk-ga. (Although, curiously enough,
this argument only show that there are some complex matrices that
cannot be written with 6 triple-products. It could still be that all
real matrices could be written as the sum of 6 triple-products of
complex matrices.)

This is definitely a more intricate problem than the other one.  I've
been thinking about it a bit and so far all I can definitely say is
that it requires a sum of more than four triple tensor products.

Here's an equivalent reformulation of the problem:

Find the smallest set of rank-1 matrices whose span includes all
matrices of the form

a b 0 0
c d 0 0
0 0 a b
0 0 c d

This is a four-dimensional space of matrices of even rank, so it must
be a strict subspace of the (at least 5-dimensional) span of rank-1
matrices.

I haven't explained yet why this is an equivalent problem, but I
thought I would mention it in case someone is able to do something
more with the problem in this form.

Hi, ilya-ga:

I'm responding to your clarification with this comment, as the
question itself is now expired.  I congratulate you on both the
interesting question and on finding a seven term solution.  One of the
purposes to which requests for clarification can be put is clearing up
what would be an acceptable answer, and that's what we've done here. 
My goal is to provide 5-star answers consistently, and in this
particular case I didn't have enough to earn that rating.

regards, mathtalk-ga