Re: ? solving linear eqn
From: Reinhard (reinhard.neuwirth_at_optus.com.au)
Date: 11/25/04
- Next message: Tim Mellor: "Re: set notation"
- Previous message: Stephen Harris: "Re: Infinite number of people toss a coin infinite times"
- In reply to: Cheng Cosine: "Re: ? solving linear eqn"
- Messages sorted by: [ date ] [ thread ]
Date: 25 Nov 2004 03:14:35 -0800
"Cheng Cosine" <acosine@ms13.url.com.tw> wrote in message news:<co2g13$309$1@vegh.ks.cc.utah.edu>...
> "Cheng Cosine" <acosine@ms13.url.com.tw> wrote in message
> news:co0p7n$oap$1@vegh.ks.cc.utah.edu...
> >
> > Given A*x = b, here x and b are vectors and A is a matrix, square or not.
> >
> > I saw the following:
> >
> > 1) given A, b and then solve for b
> >
> > but how about the following:
> >
> > 2) given x and b, solve for A?
> >
>
> Someone suggested to extend (2) into more general form that
>
> all A, x, and b are matrix. Then I can easily analysis A*x = b
>
> as what textbook usually taught to do for A*x = b as usual.
>
> But this approach just remind me another linear equation below.
>
> A*x+x*B = C
>
> Here all are matrices. A is m-by-m and B is n-by-n, while both
>
> x and C are m-by-n.
>
> I read in some linear system books called this as Lyapunov equation,
>
> and some interesting theorems are given. However, I don't see how
>
> to analysize linear problems of this kind. To be more specific, in analyzing
>
> A*x = b, I read ppl use the eigenvector or spectral expansion or more
>
> generally the SVD. Then one can see when the solution exist and unique.
>
> But I don't see any way to do analysis for A*x+x*B = C.
>
> Any suggestions?
>
> by Cheng Cosine
> Nov/24/2k4 UT
Cheng, that someone is quite right. Let us first consider how to solve
an equation in square matrices
(1) A * X = B,
With A and B given, provided A is of maximum rank, in other words
det(A) is unequal 0 (but for Christ's sake never bother to compute a
determinant, use the methods suggested below instead), the solution X
will then be found by finding the inverse of A, call it inv(A),
multiply both sides with inv(A) on the left and we get, since inv(A) *
A = E (the unity matrix with the diagonal elements =1, all other
elements =0), E*X=inv(A)*B, and since of course the unity matrix
multiplied with any matrix leaves that matrix unchanged, we find
X=inv(A)*B. What your original question started from, albeit with a
matrix A but a vector b and an unknown vector x, was to turn things
aroung and ask for A, given x and b. Guess what, in terms of matrices
the new viewpoint is not so drastically different from (1), we merely
now talk about a matrix equation
(2) X * A = B,
and again, provided A [ has maximum rank/has a non-zero determinant/is
invertable] - you guessed it, the three conditions stated in the
square brackets are equivalent, provided the condition is met, the
solution is obtained by forming inv(A), multiplying both sides (2)
with inv(A) but on the right this time, and get X=B*inv(A).
The main computational task here obviously is to find the inverse of
A. Using the time-honoured methods first developed by C.F.Gauss you
adjoin the unity matrix E to the right of A, call that structure (A|E)
and through the repeated application of "elementary row operations"
bring the A part of that adjoined structure to diagonal form. Call
that transformed diagonal matrix t(A), and the simultaneously
transformed unity matrix t(E). If t(A) is not maximum rank, ie. it has
0 elements in the diagonal, i.e. its determinant is 0, rejoice since
(1), or (2), have no solution and your work is done. If however t(A)
has maximum rank you now have a structure (t(A)|t(E)) where t(A) is a
diagonal matrix and t(E) certainly no longer looks like a unity
matrix. By taking the column vectors of t(E) one by one, call them c
and solving for vectors x in
(3) t(A) * x = c
you have obtained inv(A) as the successive x vectors are none other
than the columns of inv(A). For 3x3 or 4x4 matrices the entire 's
computation can be done on a notepad and need not take longer than 60
seconds. With a bit of practice your lecturer will accuse you
cheating!
At long last to your particular problem. Given vectors a and b solve
for a matrix X so that
(4) X * a = b
Simple. Transform a to a matrix A by interpreting a as the first
column vector of A, keep adding columns until you have a square
matrix, A. A will need to have an inverse, so you have to keep
checking. For 2- or 3- vectors this is trivial, but for larger
structures I am sure one could find an algorithm of the successive
application of "elementary row operations" a la C.F.Gauss so you don't
just randomly form A from a to then find that the result does not have
maximum rank. Let us now assume you have adjoined a to a suitable A.
You may now adjoining any columns at all to b to transform this vector
into a square matrix B and BINGO, the solution will be:
(5) X = B * inv(A)
as per the exercise we did for (2).
So, ZVK has given you the professional mathematician's answer to your
problem, I have provided the market gardener's version, what more
could you ask for?
Actually, a few very important things require an answer in connection
with (4), and I leave these for you as an exercise:
(a) are there vectors a and b for which an X cannot be found? SIMPLE,
just look at (5) and ask yourself what a would make it impossible for
A to have an inverse;
(b) obviously if there is one solution X there is an infinity of them,
and it would certainly be desirable to express this infinite solution
space in terms of a space, ie. show its dimension and perhaps write
down elements that allow the general solution to be described as a
linear combination of these elements.
Good luck. Reinhard
PS.
- Next message: Tim Mellor: "Re: set notation"
- Previous message: Stephen Harris: "Re: Infinite number of people toss a coin infinite times"
- In reply to: Cheng Cosine: "Re: ? solving linear eqn"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
