| Author |
Message
|
| Leszek Luchowski |
 Posted: Mon Jun 16, 2008 9:10 am Post subject: A linear equation with left AND right matrix multiplication |
 |
|
Forum Junior
Joined: 16 Jun 2008
Posts: 263
Location: Gliwice, Poland
|
Hello;
I am working on a problem in projective geometry and got stuck with a matrix equation that has this form:
X*A + B*Y = C
where
A, B, C are given
X and Y are unknowns to be determined
All letters represent matrices and their size is:
X: n*m
A: m*n
B: n*k
Y: k*n
C: n*n
(I know this begs the question if m+k is smaller, equal, or greater than n. That depends; I am looking for a solution that would be as general as possible, for various m's and k's, but if you can propose a way out for just one of the possible cases, say k+m>n, that will help a lot too. My n is usually 3 or 4.)
When I write out the explicit formula for each element of the sum on the left (I mean each entry of the resulting matrix which should be equal to C), it looks like it's linear with respect to the elements of X and Y.
However, I cannot for the life of me work it into a matrix form that could be solved, such as (with T meaning transpose):
A*X + BT*YT = C Â Â Â (would love to but this is wrong!)
which would lead to
[A B] * [X; YT] = C Â Â Â Â (the semicolon means the YT is stacked underneath the X)
and, in some cases at least, to a least-squares solution by one of the matrix division techniques.
Thank you in advance for any enlightment,
Leszek.
As this is my first post here, I am happy to meet you, and looking forward to some interesting exchanges. |
|
| Back to top |
|
 |
| serpicojr |
| Posted: Mon Jun 16, 2008 11:38 am Post subject: |
|
|
Forum Professor
Joined: 17 Jul 2007
Posts: 1128
Location: JRZ
|
This is definitely linear in the entries of X and Y. You can consider X and Y as vectors in an n(k+m)-dimensional space, representing the elements as (X,Y), and defining scalar multiplication and addition via:
(X,Y)+k(X',Y') = (X+kX',Y+kY')
Your equation corresponds to the map:
T(X,Y) = XA+BY
It's linear because:
T(X+kX',Y+kY') = (X+kX')A+B(Y+kY') = (XA+BY)+k(X'A+BY') = T(X,Y)+kT(X',Y')
So now you have to choose a basis for the space of matrices (X,Y). To me, the obvious basis would be the pairs of matrices of the form (Eij,0) and (0,Fpq), where Eij is the nxm matrix with a 1 in the ij position, 0 everywhere else, and Fpq is the kxn matrix with a matrix in the pq position, 0 everywhere else. Note that any (X,Y) can be written a sum of terms of the form xij(Eij,0) and ypq(0,Fpq).
Now T maps (X,Y) to the space of nxn matrices, which has basis elements of the form Grs, the nxn matrices with a 1 in the rs entry and 0 everywhere else. Thus we can express T(Eij,0) and T(0,Fpq) in terms of this basis. Indeed, we have that:
EijA = the matrix with the jth row of A in the ith row, which can be written as the sum from t = 1 to n of ajtGit
BFpq = the matrix with the qth column of B in in the pth column, which can be written as the sum from t = 1 to n of btqGtp
This should be enough for you to set up an n(k+m)xn2 matrix that represents your situation, and then you can just use typical linear algebra techniques--Gaussian elimination, e.g. |
|
| Back to top |
|
|
| Leszek Luchowski |
| Posted: Mon Jun 16, 2008 12:03 pm Post subject: |
|
|
Forum Junior
Joined: 16 Jun 2008
Posts: 263
Location: Gliwice, Poland
|
Thank you very much serpicojr for your timely and exhaustive reply. It's 9pm here in Poland so I will work through it first thing in the morning, but you have definitely made my day.
All the best, Leszek. |
|
| Back to top |
|
|
| serpicojr |
| Posted: Mon Jun 16, 2008 2:07 pm Post subject: |
|
|
Forum Professor
Joined: 17 Jul 2007
Posts: 1128
Location: JRZ
|
| No problem, glad to help out. So what's the problem you're working on, anyway? |
|
| Back to top |
|
|
| Leszek Luchowski |
| Posted: Mon Jun 16, 2008 3:05 pm Post subject: |
|
|
Forum Junior
Joined: 16 Jun 2008
Posts: 263
Location: Gliwice, Poland
|
| serpicojr wrote: |
| No problem, glad to help out. So what's the problem you're working on, anyway? |
It's a long story. Excuse my sloppy notation in what follows; I left my notes at work. I hope you will get the idea even if the formulas aren't all perfectly correct.
I began by trying to grasp the various levels of structure that can be defined in a 3D space: projective, affine, metric, Euclidean.
One of the ways they are defined is by what is invariant under linear transformations. And there are two types of those invariants: points and quadrics.
In a transformation defined by matrix A, points are transformed according to the formula Y=AX, where X qnd Y are the source and target coordinates. Quadrics are transformed by PT=QTA, where Q and P are certain sets of coefficients involved in the equation of the quadric.
So I looked for a way to identify A when two sets of vectors are known to be invariant - X to left-multiplication, QT to right-multiplication by A, so that Y=X and P=Q.
Then I wanted to generalize the problem and identify A for any given source and target points and quadrics. In other words: find a transformation A such that
AX1=Y1, AX2=Y2.... AXn=Yn
and
Q1TA=P1T... QnA=PnA.
The first set of conditions leads to a family of matrices expressed by
A=Ac + an arbitrary set of vectors of the null space of [X], added to the rows of Ac (where Ac is obtained by matrix division of Y by X)
The second set of conditions leads to another family:
A=At + an arbitrary set of vectors of the null space of [P], added to the columns of At. Again, At is obtained by matrix division.
My matrix A needs to belong to both of these families, i.e.:
A = Ac+ZxT*F = At+G*Zp
where F and G are matrices of coefficients to be identified, Zx and Zp are kernels (bases of null spaces) of [X] and [P], respectively, and T means transpose. So,
Ac-At = G*Zp - ZxT*F
which left me gasping for air and asking for your help.
Stay tuned, I hope to machete my way through it tomorrow, or the day after. Thanks for the machete.
Best, Leszek. |
|
| Back to top |
|
|
| Leszek Luchowski |
| Posted: Tue Jun 17, 2008 1:25 am Post subject: |
|
|
Forum Junior
Joined: 16 Jun 2008
Posts: 263
Location: Gliwice, Poland
|
Excuse me, serpicojr, could you please explain it in a little more detail? There must be something I don't understand, possibly in your notation. And why do you need to define scalar multiplication and addition, I thought those were standard operations?
| serpicojr wrote: |
This is definitely linear in the entries of X and Y. You can consider X and Y as vectors in an n(k+m)-dimensional space, representing the elements as (X,Y), and defining scalar multiplication and addition via:
(X,Y)+k(X',Y') = (X+kX',Y+kY')
Your equation corresponds to the map:
T(X,Y) = XA+BY |
If prime (') means transpose and k is a scalar, than X+kX' won't do because X is n*m and X' is m*n. So I suppose you mean something else, but I don't know what.
Also, what is T(X,Y) ? Is T just a symbol representing a function, defined as XA+BY, or is there more to it?
Thank you again,
Leszek. |
|
| Back to top |
|
|
| serpicojr |
| Posted: Tue Jun 17, 2008 8:01 am Post subject: |
|
|
Forum Professor
Joined: 17 Jul 2007
Posts: 1128
Location: JRZ
|
Okay, so for me, prime (') does not represent transpose. When I use it, I just mean I'm introducing another object of the same type as the thing that's being primed. So X' is a matrix of the same size as X. For transpose, I use (T), so X transpose is XT.
Anyway, yes, the letter T was representing a function from the space of pairs of nxm and kxn matrices, which I'll call V, to the space of nxn matrices W. First, I was checking that V and W were vector spaces. W clearly is--I can add matrices and multiply them by scalars. But what about pairs of matrices in V? If you know about direct sums, then V is the direct sum of the space of nxm matrices and the space of kxn matrices, so it's a vector space. If you don't, then I was defining how you did addition and scalar multiplication on V, and this verified that V was a vector space.
Then I checked that T was linear, and this implies that I can represent T as a matrix if I choose a basis for V and a basis for W. I wrote down the simplest basis for each space that I could come up with, and then I was able to obtain linear equations representing how T behaved on these basis elements--i.e., for each basis vector b (which is really a pair of matrices) of V, I express T(b) as a sum of basis vectors of W. This allows me to represent T by a matrix.
Now the original equation you wanted to solve was T(X,Y) = C for some specific C. So express C as a sum of basis elements of W, and now you have a matrix equation--namely, the equation is the matrix representing T multiplied by the vector of entries of X and Y equals the vector of entries of C.
Then I worked out the equations to express the entries of T. |
|
| Back to top |
|
|
| Leszek Luchowski |
| Posted: Thu Jun 19, 2008 12:54 am Post subject: |
|
|
Forum Junior
Joined: 16 Jun 2008
Posts: 263
Location: Gliwice, Poland
|
Howdy;
thanks for the explanation. I am now trying to solve it by representing the equation
X*A + B*Y = C
as
D*W=E
where:
- D is a (n*n)*(n*(k+i)) array containing elements of A and B, duly reshuffled,
- W is a column vector of length n*(k+i), filled with elements of X and Y,
- E is a column vector of length n*n, filled with elements of C.
I feel in principle this should work, but I am still struggling to program the correct arrangements of elements in these reorganized formats. The multitude of indices is a bit confusing.
Stay tuned,
Leszek. |
|
| Back to top |
|
|
| Leszek Luchowski |
| Posted: Fri Jun 20, 2008 1:08 am Post subject: |
|
|
Forum Junior
Joined: 16 Jun 2008
Posts: 263
Location: Gliwice, Poland
|
I think I have got it. Written a Scilab function implementing the idea. Illustrative fragments of header follow; will post the whole function if anyone is interested. Seems to work, but don't blame me if it doesn't.
Scilab is a free software similar to Matlab; double slashes (//) mean comments.
function [X,Y]=K3Sudoku(A,B,C)
// solves problem of type
// X*A + B*Y = C
(...)
// Bring your equation to form ColVect(C)=BigMatr*XYVect
// where:
// ColVect(C) is C in (n*n)*1 format (one column, n*n rows)
// BigMatr represent the sum of left- and right-product
// VXY is [X; Y] also in 1-column format
Thank you again, serpicojr,
best regards to all -
Leszek. |
|
| Back to top |
|
|
| serpicojr |
| Posted: Fri Jun 20, 2008 7:09 am Post subject: |
|
|
Forum Professor
Joined: 17 Jul 2007
Posts: 1128
Location: JRZ
|
| Good luck with your research! |
|
| Back to top |
|
|
|
|
|
