what is the inverse operation of Kronecker product?

Dear all,

I want to ask what is the inverse operation of Kroneck product?

More specifically, we know that matrix operation

A*X*B=kron(A, B')*vec(X)

where kron is the Kronecker product of matrices as defined in matlab; vec(X)
is the stacked vector version of matrix X. All matrices are square...

Now I want to reverse the operation, suppose I have a big matrix C,

how to find A and B to get C=kron(A, B')?

Under what condition these A and B cannot be found? Then how to find them
approximately, i.e., optimal in the mean-square sense or under other
criteria? That's to say, find A and B, such that kron(A, B')=C1 where C1 is
a reasonably good approximation to C?

Thanks a lot,

-Walala

walala:

Maybe if you gave the homework questions verbatim from the Prof, we could be
of more help. It seems your interpretation of your tasks is confusing some
people. Then again, if you really knew the questions, you wouldn't be
posting for answers.

Jim

"walala" <mizhael@yahoo.com> wrote in message
news:bsptnn$8vh$1@mozo.cc.purdue.edu...
> Dear all,
>
> I want to ask what is the inverse operation of Kroneck product?
>
> More specifically, we know that matrix operation
>
> A*X*B=kron(A, B')*vec(X)
>
> where kron is the Kronecker product of matrices as defined in matlab;
vec(X)
> is the stacked vector version of matrix X. All matrices are square...
>
> Now I want to reverse the operation, suppose I have a big matrix C,
>
> how to find A and B to get C=kron(A, B')?
>
> Under what condition these A and B cannot be found? Then how to find them
> approximately, i.e., optimal in the mean-square sense or under other
> criteria? That's to say, find A and B, such that kron(A, B')=C1 where C1
is
> a reasonably good approximation to C?
>
> Thanks a lot,
>
> -Walala
>
>

"Jim Gort" <jgort@comcast.net> wrote in message
news:NF4Ib.697310$Fm2.601200@attbi_s04...
> walala:
>
> Maybe if you gave the homework questions verbatim from the Prof, we could
be
> of more help. It seems your interpretation of your tasks is confusing some
> people. Then again, if you really knew the questions, you wouldn't be
> posting for answers.
>
> Jim
>
> "walala" <mizhael@yahoo.com> wrote in message
> news:bsptnn$8vh$1@mozo.cc.purdue.edu...
> > Dear all,
> >
> > I want to ask what is the inverse operation of Kroneck product?
> >
> > More specifically, we know that matrix operation
> >
> > A*X*B=kron(A, B')*vec(X)
> >
> > where kron is the Kronecker product of matrices as defined in matlab;
> vec(X)
> > is the stacked vector version of matrix X. All matrices are square...
> >
> > Now I want to reverse the operation, suppose I have a big matrix C,
> >
> > how to find A and B to get C=kron(A, B')?
> >
> > Under what condition these A and B cannot be found? Then how to find
them
> > approximately, i.e., optimal in the mean-square sense or under other
> > criteria? That's to say, find A and B, such that kron(A, B')=C1 where C1
> is
> > a reasonably good approximation to C?
> >
> > Thanks a lot,
> >
> > -Walala
> >

Dear Jim,

This really isn't my professor's homework problem... our school is now in
break so there are no damn homeworks right now...

This is a problem I am currently interested in... please tell me which part
of my description confuses you? Then I can make myself clearer...

Rgs,

-Walala

In article <bsptnn$8vh$1@mozo.cc.purdue.edu>, walala <mizhael@yahoo.com> wrote:

>I want to ask what is the inverse operation of Kroneck product?

>More specifically, we know that matrix operation

>A*X*B=kron(A, B')*vec(X)

>where kron is the Kronecker product of matrices as defined in matlab; vec(X)
>is the stacked vector version of matrix X. All matrices are square...

>Now I want to reverse the operation, suppose I have a big matrix C,

>how to find A and B to get C=kron(A, B')?

Algebraically, this is the tensor product of two linear operators, which 
I'll write as C = A \tensor B'.  For vectors u,v,w,z let
F(u,v,w,z) = (u \tensor w)' C (v \tensor z).  Then a necessary
and sufficient condition for C to be a tensor product is

F(u1,v1,w1,z1) F(u2,v2,w2,z2) = F(u1,v1,w2,z2) F(u2,v2,w1,z1)

for all vectors u1,v1,w1,z1,u2,v2,w2,z2.  Of course by linearity 
it suffices to do this for u1,v1,w1,z1,u2,v2,w2,z2 in a basis
of R^n.  Using the standard basis this can be written as

C_{i_1k_1,j_1l_1} C_{i_2k_2,j_2l_2} = C_{i_1k_2,j_1l_2} C_{i_2k_1,j_2l_1}

Moreover, if this condition holds A and B can be found as 
follows:

We may assume F is not identically 0.  Fix some u0, v0, w0, z0 so that
F(u0,v0,w0,z0) = 1.  Then Q1(w,z) = F(u_0,v_0,w,z) is a bilinear form,
so there is an n x n matrix B such that Q1(w,z) = w' B' z.  
Similarly, Q2(u,v) = F(u,v,w0,z0) is a bilinear form, and there is
an n x n matrix A such that Q2(u,v) = u' A v.  Then
F(u,v,w,z) = F(u,v,w0,z0) F(u0,v0,w,z) = (u' A v) (w' B' z)
i.e.
(u \tensor w)' C (v \tensor z) = (u \tensor w)' (A \tensor B') (v \tensor z)
and since tensor products of vectors span R^(n^2), we get
C = A \tensor B'.

Robert Israel                                israel@math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel 
University of British Columbia            
Vancouver, BC, Canada V6T 1Z2

The inverse solutions are discussed in

http://www.mathcs.emory.edu/~nagy/conferences/2003/SIAM_LA.pdf

Maybe this answers your questions.

Gregor


"walala" <mizhael@yahoo.com> wrote in message
news:bsptnn$8vh$1@mozo.cc.purdue.edu...
> Dear all,
>
> I want to ask what is the inverse operation of Kroneck product?
>
> More specifically, we know that matrix operation
>
> A*X*B=kron(A, B')*vec(X)
>
> where kron is the Kronecker product of matrices as defined in matlab;
vec(X)
> is the stacked vector version of matrix X. All matrices are square...
>
> Now I want to reverse the operation, suppose I have a big matrix C,
>
> how to find A and B to get C=kron(A, B')?
>
> Under what condition these A and B cannot be found? Then how to find them
> approximately, i.e., optimal in the mean-square sense or under other
> criteria? That's to say, find A and B, such that kron(A, B')=C1 where C1
is
> a reasonably good approximation to C?
>
> Thanks a lot,
>
> -Walala
>
>

"Robert Israel" <israel@math.ubc.ca> wrote in message
news:bsrb1a$79k$1@nntp.itservices.ubc.ca...
> In article <bsptnn$8vh$1@mozo.cc.purdue.edu>, walala <mizhael@yahoo.com>
wrote:
>
> >I want to ask what is the inverse operation of Kroneck product?
>
> >More specifically, we know that matrix operation
>
> >A*X*B=kron(A, B')*vec(X)
>
> >where kron is the Kronecker product of matrices as defined in matlab;
vec(X)
> >is the stacked vector version of matrix X. All matrices are square...
>
> >Now I want to reverse the operation, suppose I have a big matrix C,
>
> >how to find A and B to get C=kron(A, B')?
>
> Algebraically, this is the tensor product of two linear operators, which
> I'll write as C = A \tensor B'.  For vectors u,v,w,z let
> F(u,v,w,z) = (u \tensor w)' C (v \tensor z).  Then a necessary
> and sufficient condition for C to be a tensor product is
>
> F(u1,v1,w1,z1) F(u2,v2,w2,z2) = F(u1,v1,w2,z2) F(u2,v2,w1,z1)
>
> for all vectors u1,v1,w1,z1,u2,v2,w2,z2.  Of course by linearity
> it suffices to do this for u1,v1,w1,z1,u2,v2,w2,z2 in a basis
> of R^n.  Using the standard basis this can be written as
>
> C_{i_1k_1,j_1l_1} C_{i_2k_2,j_2l_2} = C_{i_1k_2,j_1l_2} C_{i_2k_1,j_2l_1}
>
> Moreover, if this condition holds A and B can be found as
> follows:
>
> We may assume F is not identically 0.  Fix some u0, v0, w0, z0 so that
> F(u0,v0,w0,z0) = 1.  Then Q1(w,z) = F(u_0,v_0,w,z) is a bilinear form,
> so there is an n x n matrix B such that Q1(w,z) = w' B' z.
> Similarly, Q2(u,v) = F(u,v,w0,z0) is a bilinear form, and there is
> an n x n matrix A such that Q2(u,v) = u' A v.  Then
> F(u,v,w,z) = F(u,v,w0,z0) F(u0,v0,w,z) = (u' A v) (w' B' z)
> i.e.
> (u \tensor w)' C (v \tensor z) = (u \tensor w)' (A \tensor B') (v \tensor
z)
> and since tensor products of vectors span R^(n^2), we get
> C = A \tensor B'.
>
> Robert Israel                                israel@math.ubc.ca
> Department of Mathematics        http://www.math.ubc.ca/~israel
> University of British Columbia
> Vancouver, BC, Canada V6T 1Z2

Dear Robert,

Thanks a lot for your answer. I tried

K=kron(A, A) and I successfully got [A, A]=inv_kron(K) sometimes;

If I do

K=kron(A, B) then most of time [A, B]=inv_kron(K) will not reproduce A and B
exactly... That's ok!

Now what if I want to impose some structure on the decomposition?

For example, for certain K, I want to obtain

K=kron(A, B)*U+kron(C, D)*V

where A, B, C, D is restricted to some easy-to-compute structure, such as
orthogonal, etc... U and V should be diagonal..

K=kron(A, B)*U+kron(C, D)*V+kron(E, F)*W...

Is there any existing previous work which tackled this kind of problem?

Thanks a lot and happy new year!

-Walala

"GTO" <gregor_o@NOSPAMyahoo.com> wrote in message
news:6OaIb.3261$Dx4.2523@newssvr27.news.prodigy.com...
> The inverse solutions are discussed in
>
> http://www.mathcs.emory.edu/~nagy/conferences/2003/SIAM_LA.pdf
>
> Maybe this answers your questions.
>
> Gregor
>
>

Dear Gregor,

Thanks a lot for your answer. The link helped a lot!

I tried

K=kron(A, A) and I successfully got [A, A]=inv_kron(K) sometimes;

If I do

K=kron(A, B) then most of time [A, B]=inv_kron(K) will not reproduce A and B
exactly... That's ok!

Now what if I want to impose some structure on the decomposition?

For example, for certain K, I want to obtain

K=kron(A, B)*U+kron(C, D)*V

where A, B, C, D is restricted to some easy-to-compute structure, such as
orthogonal, etc... U and V should be diagonal..

K=kron(A, B)*U+kron(C, D)*V+kron(E, F)*W...

Is there any existing previous work which tackled this kind of problem?

Thanks a lot and happy new year!

-Walala

Hi Robert

I have been looking for a good introduction to tensor albegra, working
notation,
and some insightful explanations. I've have no luck so far on the web.

Could you point me to a good source to get started with tensors? given
that i can work with basic vectors, matrices and standard linear
algebra....

Thnx



israel@math.ubc.ca (Robert Israel) wrote in message news:<bsrb1a$79k$1@nntp.itservices.ubc.ca>...
> In article <bsptnn$8vh$1@mozo.cc.purdue.edu>, walala <mizhael@yahoo.com> wrote:
> 
> >I want to ask what is the inverse operation of Kroneck product?
>  
> >More specifically, we know that matrix operation
>  
> >A*X*B=kron(A, B')*vec(X)
>  
> >where kron is the Kronecker product of matrices as defined in matlab; vec(X)
> >is the stacked vector version of matrix X. All matrices are square...
>  
> >Now I want to reverse the operation, suppose I have a big matrix C,
>  
> >how to find A and B to get C=kron(A, B')?
> 
> Algebraically, this is the tensor product of two linear operators, which 
> I'll write as C = A \tensor B'.  For vectors u,v,w,z let
> F(u,v,w,z) = (u \tensor w)' C (v \tensor z).  Then a necessary
> and sufficient condition for C to be a tensor product is
> 
> F(u1,v1,w1,z1) F(u2,v2,w2,z2) = F(u1,v1,w2,z2) F(u2,v2,w1,z1)
> 
> for all vectors u1,v1,w1,z1,u2,v2,w2,z2.  Of course by linearity 
> it suffices to do this for u1,v1,w1,z1,u2,v2,w2,z2 in a basis
> of R^n.  Using the standard basis this can be written as
> 
> C_{i_1k_1,j_1l_1} C_{i_2k_2,j_2l_2} = C_{i_1k_2,j_1l_2} C_{i_2k_1,j_2l_1}
> 
> Moreover, if this condition holds A and B can be found as 
> follows:
> 
> We may assume F is not identically 0.  Fix some u0, v0, w0, z0 so that
> F(u0,v0,w0,z0) = 1.  Then Q1(w,z) = F(u_0,v_0,w,z) is a bilinear form,
> so there is an n x n matrix B such that Q1(w,z) = w' B' z.  
> Similarly, Q2(u,v) = F(u,v,w0,z0) is a bilinear form, and there is
> an n x n matrix A such that Q2(u,v) = u' A v.  Then
> F(u,v,w,z) = F(u,v,w0,z0) F(u0,v0,w,z) = (u' A v) (w' B' z)
> i.e.
> (u \tensor w)' C (v \tensor z) = (u \tensor w)' (A \tensor B') (v \tensor z)
> and since tensor products of vectors span R^(n^2), we get
> C = A \tensor B'.
> 
> Robert Israel                                israel@math.ubc.ca
> Department of Mathematics        http://www.math.ubc.ca/~israel 
> University of British Columbia            
> Vancouver, BC, Canada V6T 1Z2

Hello EnTn,

An inexpensive source is the Dover book "Tensors, Differential Forms, and
Variational Principles" by Lovelock and Rund. ISBN 0-486-65840-6

Another book is "Introducing Einstein's Relativity" by D'Inverno. While this
is a graduate level book, it does have some good introductory explanations
of tensors. ISBN 0-19-859686-3

You also may want to go peruse books on mathematical physics as this is
where you can find a some introductory material on tensors.

IHTH,
Clay




"EnTn" <entropic_tendencies@yahoo.co.uk> wrote in message
news:1d75390b.0401070714.17124831@posting.google.com...
> Hi Robert
>
> I have been looking for a good introduction to tensor albegra, working
> notation,
> and some insightful explanations. I've have no luck so far on the web.
>
> Could you point me to a good source to get started with tensors? given
> that i can work with basic vectors, matrices and standard linear
> algebra....
>
> Thnx
>

Thanks for the references Clay,

Managed to find D'Inverno in my library...


"Clay S. Turner" <CSTurner@WSE.Biz> wrote in message news:<SgYKb.916$TR6.451@bignews3.bellsouth.net>...
> Hello EnTn,
> 
> An inexpensive source is the Dover book "Tensors, Differential Forms, and
> Variational Principles" by Lovelock and Rund. ISBN 0-486-65840-6
> 
> Another book is "Introducing Einstein's Relativity" by D'Inverno. While this
> is a graduate level book, it does have some good introductory explanations
> of tensors. ISBN 0-19-859686-3
> 
> You also may want to go peruse books on mathematical physics as this is
> where you can find a some introductory material on tensors.
> 
> IHTH,
> Clay
> 
> 
> 
> 
> "EnTn" <entropic_tendencies@yahoo.co.uk> wrote in message
> news:1d75390b.0401070714.17124831@posting.google.com...
> > Hi Robert
> >
> > I have been looking for a good introduction to tensor albegra, working
> > notation,
> > and some insightful explanations. I've have no luck so far on the web.
> >
> > Could you point me to a good source to get started with tensors? given
> > that i can work with basic vectors, matrices and standard linear
> > algebra....
> >
> > Thnx
> >