I want to represent a fairly simple 8x8 matrix with 
a sum of several Kronecker (or tensor) products of three 
2x2 matrices.  The matrix in question has 8 nonzeros 
and looks like this: 

      1 0 0 0 0 0 1 0 
      0 1 0 0 0 0 0 1 
      0 0 0 0 0 0 0 0 
  A = 0 0 0 0 0 0 0 0 
      0 0 0 0 0 0 0 0 
      0 0 0 0 0 0 0 0 
      1 0 0 0 0 0 1 0 
      0 1 0 0 0 0 0 1 

and I need to use the MINIMAL number of products possible. 

Just to clarify a bit: suppose X, Y, and Z are 2x2 matrices. 
The Kronecker product of the three is an 8x8 matrix 
(in Matlab notation it will be kron(X,kron(Y,Z)) - changing 
the order will permute the resulting matrix, but won't change 
the entries).  

I cannot match A shown above with a single product, so I have 
to use more than one: 

A = kron(X_1,kron(Y_1,z_1)) +  kron(X_2,kron(Y_2,Z_2)) + ... 

and the question is: how far do I have to go?  

Obviously, there is a trivial solution with 8 products: one can match 
each of the 1s in A with a simple product of three matrices with all 
zeros and single 1 put in the right place.  For example, the product 
kron(X,kron(Y,Z)) of three identical matrices 

             1   0 
X = Y = Z =        
             0   0 

will be the 8x8 matrix of zeros with the only 1 in (1,1) position.  
Similarly, I can construct seven other products that put 1s in the 
right places, so when I add them all together I get A using eight 
products.  

This is a simple, but suboptimal solution (one can do better than with 
8 products).  Of course, X, Y, and Z can have more than one nonzero and 
the entries don't have to be integer.  I am looking for the OPTIMAL 
SOLUTION (minimal number of products) with a PROOF of optimality. 
(I am not looking for information about the properties of Kronecker 
products or related stuff). 

Thanks. Please let me know if I need to clarify the problem statement.

---

Request for Question Clarification by rbnn-ga on 01 Nov 2002 17:36 PST

Is what you are asking this?

Let E be a fully parenthesized expression in variables v_1, v_2, ...
,v_n , where the only symbols allowed in E are parentheses, + , the
kronecker product, and the variables v_1,...,v_n .

The cost of E is defined as the number of kronecker product symbols
occurring in E .

Find the E of minimum cost that has the property that there exist two
dimensional complex matrices w_1,...,w_n such that, when v_i is set
w_i, the resulting expression evaluates to A .

---

Request for Question Clarification by rbnn-ga on 01 Nov 2002 17:47 PST

Regarding my previous request for clarification: I think the main
points I wanted to clarify are whether expressions of the form

(v_1+v_2) kronecker (v_3+v_v) 

are to be allowed; (I assume yes), and whether multiplication by a
scalar or subtraction or matrix multiplication is allowed (I assume
no)

---

Clarification of Question by ilya-ga on 01 Nov 2002 18:39 PST

The question is how many expressions of the form 
kron(X,kron(Y,Z)) one needs to add to get the matrix 
defined in the problem.  It's up to you what X, Y, and 
Z in each product are.  I am not sure what your question 
is.  If you are asking wheather 

(v_1+v_2) kronecker (v_3+v_4)  

are allowed, then why don't you just name Y=v_1+v_2 and Z=v_3+v_4 
and replace the above with 

Y kronecker Z.  

Again, X, Y, and Z are any 2x2 matrices.  I'm not sure what 
v_1+v_2 gives you over just uing one matrix Y instead?  

I want to represent A in a specific form 

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

where all the matrices in the right hand side are 2x2 and 
the objective is to minimize the number of terms. 

Please let me know if I can clarify further. 
Thanks

---

Request for Question Clarification by rbnn-ga on 01 Nov 2002 20:57 PST

Are terms like kron((kron(x,y)+kron(z,q)),r) legal?

---

Clarification of Question by ilya-ga on 01 Nov 2002 23:17 PST

No, kron((kron(x,y)+kron(z,q)),r) is not allowed.  Sorry, I guess 
I didn't understad your previous question.  

All the terms should have exactly three 2x2 matrices and should 
be exactly of the form kron(X,kron(Y,Z)).  Even kron() "reodering" 
kron(kron(X,Y),Z) is not allowed (although I suspect the "reordered" 
expression can be transformed to the "proper" form by permuting 
X,Y, and Z).

Hello ilya:

My computations have also shown that the minimal number of products is
four.

While I was not able to prove this *mathematically*, I was able to
show it using Maple (a computer algebra program). I basically set up
symbolic matrices for the 1-, 2-, and 3-product cases and then tried
to solve the resulting systems of equations once the individual matrix
element were equated to the corresponding values in A. There were no
solutions to the systems for the 1-, 2-, and 3-product cases.

Then I extended the model for the 4-product case and started to solve
the system. I let the calculation run *all night* and it was still
chugging away this morning with no end in sight (so I interrupted it).
In the meantime, I had been able to come up with the following
four-product example "in my head."


       1   0            1   0             1   0
X_1 =            Y_1 =             Z_1 = 
       0   0            0   0             0   1


       0   1            0   1             1   0
X_2 =            Y_1 =             Z_1 = 
       0   0            0   0             0   1


       0   0            0   0             1   0
X_3 =            Y_3 =             Z_3 = 
       1   0            1   0             0   1


       0   0            0   0             1   0
X_4 =            Y_4 =             Z_4 = 
       0   1            0   1             0   1


I'm not sure whether this (and the obvious permutations of it) are the
*only* 4-product examples, but your question didn't really call for
that sort of assurance.

If you would like me to "pretty up" my Maple worksheet and post it
here, I'd be happy to do that for you. Please let me know.

Links of interest:

Maple
http://www.maplesoft.com

Block Matrices
http://delta.cs.cinvestav.mx/~schapa/red/alglineal/node56.html

If you need any clarification of the information I have provided, 
please ask using the Clarification feature and provide me with 
additional details as to what you are looking for. As well, please 
allow me to provide you with clarification(s) *before* you rate this 
answer. 
         
Thank you.          
         
websearcher-ga         
         
 
Search Strategy: 
 
"Kronecker product" matrices
://www.google.com/search?q=%22Kronecker+product%22+matrices&hl=en&lr=&ie=UTF-8&safe=off&start=10&sa=N

---

Clarification of Answer by websearcher-ga on 03 Nov 2002 16:40 PST

Hi ilya:

The Maple worksheet that shows that the 1-, 2- and 3-product
summations don't work can now be found at:

http://www.silvermasters.com/utilities/kron.rtf

websearcher-ga

Thanks!

ilya-ga,

If you allow the ordering kron(kron(x,y),z) then you can do it with 4
terms, since your original matrix "factorizes" into a kronecker
product

A = kron(B,C), where   B =   1  0  0  1        C =  1  0
                             0  0  0  0             0  1
                             0  0  0  0
                             1  0  0  1


And B can then be represented as a sum of 4 kronecker products of two
matrices. I don't know how to prove that 4 is optimal but I would
guess that it is.

If, as you say, you don't allow kron(kron(x,y),z)) but only
kron(x,kron(y,z)), I think you are wrong in stating that this is
equivalent to the other ordering: what you can get by permuting x,y,z
is a permuted version of your matrix, which if I understand correctly
is not admissible. In that case, I don't see an obvious way to improve
over the trivial sum of 8 kronecker products, but again have no idea
how to prove this...

-dannidin

ilya,

Four is indeed the optimal number.  First note that any solution to
the triple tensor problem
must also solve the smaller problem of producing the matrix

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

which we show cannot be written as a sum of fewer than four tensor
products of 2x2 matrices.

Nothing about this problem uses the multiplicative structure of 2x2
matrices; all that is important
is that they form a vector space of dimension 4, with a basis given by
the matrices

1 0   0 1   0 0   0 0
0 0   0 0   1 0   0 1.

Call these matrices e_1, e_2, e_3, and e_4, respectively.  Since we
are only interested
in these matrices (for the stated problem, at least) as elements of a
vector space, it's
conceptually simpler to re-write elements of this vector space as row
and column vectors.
The goal, which we know can be written as e_1 x e_1 + e_2 x e_2 + e_3
x e_3 + e_4 x e_4,
now becomes the identity matrix

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

which is still a 4-by-4 matrix, but constructed differently.  In
particular, we wish to write this
matrix as a sum of tensor products of the following form:

                      e       ae be ce de
a b c d  tensor    f  =    af bf cf df
                      g       ag bg cg dg
                      h       ah bh ch dh

This is a 4x4 matrix of rank 1; every row is a multiple of the row
vector, and every column is a
multiple of the column vector.  In particular, the span of the columns
of the matrix is a
subspace of dimension 1.  What happens when we add two such matrices? 
Let v_1 be the
column vector in the first tensor product, and v_2 be the column
vector in the second.  Then
every column of the sum is a linear combination of v_1 and v_2; in
particular, the set of columns
of the sum spans at most the vector space of dimension 2 spanned by
v_1 and v_2.  In other
words, the sum of two rank-1 matrices has rank at most 2.  Similarly,
the sum of k rank-1 matrices
has rank at most k.  Since the identity matrix has rank 4 (its columns
span a space of dimension
4), it cannot be written as a sum of fewer than 4 rank-1 matrices.

For the identity matrix, at least, the solution is far from unique. 
To give just one example of
an alternate solution, translated back to the original setting of
tensor products of 2x2 matrices,
take the sum of the following tensor products, where 's' represents
the square root of 1/2:

A = s  s   B = s -s   C = 0  0   D = 0  0
    0  0       0  0       s  s       s -s

kron(A,A) + kron(B,B) + kron(C,C) + kron(D,D)

which can then be tensored by the 2-by-2 identity matrix to solve the
original problem.

poincare-ga: That is a beautiful argument. 

Quick question, though - can you explain a bit more why it suffices to
show that the that matrix [1 0 0 1;0 0 0 0;0 0 0 0;1 0 0 1] cannot be
be represented as the sum of four 2x2 tensor products?

The problem is equivalent to a rank approximation in a different
linear space and it is solved with the Singular Value Decomposition.
Indeed the four term solution is optimal because that is the
"Kronecker rank" of the matrix in that space. One can find the closest
Kronecker product to a given matrix of non-prime dimensions. See

C. Van Loan, N. Pitsianis, Approximation with Kronecker Products,
Linear Algebra for Large Scale and Real Time Applications (ed. M. S.
Moonen and G. H. Golub), Kluwer Publications, pg 293-314, 1993.

N. P. Pitsianis, The Kronecker Product in Approximation and Fast
Transform Generation, PhD Thesis, Department of Computer Science,
Cornell University, Jan. 1997.

N. P. Pitsianis, Some Properties of the Strong Kronecker Product,
International Conference on Computational Engineering Science '98,
Atlanta, GA, Oct 1998, in "Modeling and Simulation Based Engineering",
Volume I, pages 433-8, Editors S. N. Alturi and P. E. O'Donoghue, Tech
Science Press, July 1998.

Thanks for the answer and for all the comments.  
I can see that the matrix can be written as a sum of four terms 
and a "proof by Maple" that it's impossible to do with fewer terms 
is sufficeint.  

I didn't quite follow  poincare-ga's argument.  Why is it sufficient to 
show that the [1 0 0 1; 0 0 0 0; 0 0 0 0; 1 0 0 1] matrix cannot be 
represented with fewer than four Kronecker products?  

Thanks to npp-ga for the pointers to papers and the thesis.  I'll certainly 
have a look. 

I do have a follow-up question and I will post it now.  Essentially 
it's the same question about a permutation of matrix A.  I thought 
that it will be trivial to extend the result from A to its permutation, 
but I don't see how to do that. 

Thanks!

rbnn and ilya:

re: Why is it sufficient to show that [1 0 0 1;0 0 0 0;0 0 0 0;1 0 0
1] requires four terms?

If you take an arbitrary linear combination of triple tensor products
of 2 x 2 matrices and restrict your attention to the
[1,3,5,7],[1,3,5,7] submatrix, that 4 x 4 matrix is itself a linear
combination of double tensor products of 2 x 2 matrices, where the
coefficients in the linear combination come from the original
coefficients each multiplied by the (1,1) entry of the remaining 2 x 2
matrix in the triple product.  So if a three-term sum existed for the
8 x 8 matrix, it would give a three-term sum for the matrix [1 0 0 1;0
0 0 0;0 0 0 0;1 0 0 1].

poincare-ga: Ah! How simple! And yet I just couldn't see it. Anyway,
your whole proof is impressively elegant and insightful. (Are you a
Putnam winner, or an algebra professor somewhere?)