| Posted on Tuesday, 24 June, 2003 - 03:53 pm: |
Consider the matrix M in which the entry in the ith row, jth column (i and j go from 0 to n) is xi j
E.g. When n=1 we get:
[ 1 x0 ]
[ 1 x1 ]
Is it possible to express the general inverse (if it exists) in a "simple" way?
Marcos
| Posted on Tuesday, 24 June, 2003 - 04:47 pm: |
As far as I know, there isn't a "simple" way to represent the inverse of a matrix. Indeed, it does not have one if det M = 0.
For a good account of how to compute the inverse of an arbitrary matrix by recursively evaluating submatrices (and all other elements of matrix algebra), go here .
As you're talking of a "special case", you could work it out algebraically for various matrices and see what happens - I doubt there's any other way. Or perhaps a product of matrices somehow?
| Posted on Tuesday, 24 June, 2003 - 05:44 pm: |
Marcos, The matrix you're dealing with is known as a Vandermonde matrix. It is nonsingular as long as the xis are distinct. Suppose that the inverse of M is A with entries (aij. Then define the polynomial
| Pj(x)= |
å i | aij xi |
. It is now clear that (MA)i=Pj(xi). We want this to be 0 when i ¹ j and 1 when i=j. Can you see how to construct polynomials with this property? David
| Posted on Tuesday, 24 June, 2003 - 06:49 pm: |
David,
Thanks for the reply...
One question: Am I looking for an (explicit) expression for aij or a method for calculating aij (given n)
Marcos
| Posted on Tuesday, 24 June, 2003 - 08:00 pm: |
Simply construct the polynomial Pj (xi ).It does magic.
love arun
| Posted on Monday, 07 July, 2003 - 01:54 pm: |
Okay,
After not thinking about this problem for 2 weeks I decided to have another knack at it.
I don't seem to be getting Arun's phrase of "simply construct", without actually explicitly working out aij .
Could I have a little shove in the right direction please? (I'm working on a way to generate the polynomial given n, but I don't even think this is what I'm meant to be doing)
Marcos
| Posted on Tuesday, 08 July, 2003 - 04:50 pm: |
Marcos,
Look at this property,
Now,try and construct a polynomial using this property alone and nothing else.(In other words,simply find a function which satisfies the above property.)
Hint (in white)
if
f(x)
= 0 ,x=a
= 1 ,x=b
then f(x) = (x-a)/(b-a) satisfies the condition
love arun
| Posted on Tuesday, 08 July, 2003 - 05:56 pm: |
I realise now I've been quite stupid (clearly if f(x) is a polynomial and f(a)=0 then (x-a)|f(x), a result I think we proved in O-level!). I get:
| Pj(xi)= |
Õ | [(xi-xr)/(xj-xr)] |
where the product is over 0 £ r £ n, r ¹ j
Is this correct?
Now I'll go expand it (shouldn't be that hard I hope? )
Marcos
| Posted on Wednesday, 09 July, 2003 - 06:38 am: |
f(x)=(x-a)(x-b)(x-c)
therefore the coefficients are,
1,a+b+c,ab+bc+ca,abc
love arun
| Posted on Wednesday, 09 July, 2003 - 08:30 am: |
Arun, shouldn't they be 1, -(a+b+c), (ab+bc+ac), -abc? Am I meant to get an explicit (and concise) formula for aij? I get
| aij=(-1)2n-i Sij/ |
Õ | (xj-xr) |
(product as before) where S0j=1, Sij= sum of all possible arrangements of xr (r ¹ j)taken i at a time. Is this as simple as it gets?
(It's times like this I wish I knew TE X)
Marcos
| Posted on Wednesday, 09 July, 2003 - 05:42 pm: |
I think the answer is correct.
As for Latex,
 Latex Commandslatexcomm.txt (2 k) |
I have compiled some of the Latex Commands(along with the Nrich syntax)that you would like to use here at Nrich in the above file.
I have not described the functions as such so you would have try them out here itself in Nrich( by previewing them and not posting them ).Once you try them out, you would be pretty comfortable soon.
Good Luck TE X - ing!
love arun
| Posted on Wednesday, 09 July, 2003 - 07:58 pm: |
And i also found the site from where i had noted down those commands.
Latex Commands
love arun
| Posted on Wednesday, 09 July, 2003 - 08:25 pm: |
Arun,
Thanks a lot for the LA TE X commands. I think I'll go download some TE x compiler and start writing up some maths stuff aswell...
Marcos
P.S. In case anyone was curious I required the inverse when trying (among other things) to construct the best polynomial to fit a given set of data.
The fact that the matrix has a name suggests that it possibly has some more interesting applications/properties. Can anyone refer me to anything about it (if it's not that advanced)?
| Posted on Thursday, 10 July, 2003 - 08:13 am: |
Before putting this problem to rest completely, could someone (possibly Arun - seeing as he's a Computer Scientist) suggest a way of constructing an algorithm to calculate Sij (that can be implemented in, say, C using only fundamental libraries - ie. no math.h)
Any algorithm I come up with seems a bit too overcomplicated for such a seemingly basic task...
Thanks,
Marcos
| Posted on Saturday, 12 July, 2003 - 07:41 am: |
Let x[n] be the array of factors.
Then for sum ab,
sum=0;
for(i=0;i < n;i++)
for(j=i+1;j < n;j++)
sum=sum+x[i]*x[j];
coefficient=sum;
(Can you see why this works?Put down a n x n matrix wherein aij =x[i]*x[j].Look at the upper(or lower triangle) of this matrix.)
However,making the above idea work for sum abc would be a touch difficult.So i modify my above code as,
sum=0;
for(i=0;i < n;i++)
for(j=0;j < n;j++)
if(i!=j)
sum=sum+x[i]*x[j];
coefficient=sum/2;
(Can you see why sum/2 comes here?If yes,then this logic can be extended for sum abc, sum abcd and so on)
by now you would have realised that for sum abc, sum abcd and further ... we need to increase the number of loops which means for each coefficient one would have to write independent codes.This is not a feasible option.What is the way to avoid this??Answer : Recursion.
These are the programs,
 Normal Methodcoeff.cpp ( < 1 k) |
 Recursivecoeff2.cpp (1 k) |
love arun
| Posted on Saturday, 12 July, 2003 - 09:04 am: |
Arun thanks very very much!
That's extremely clever. I think so anyway, with my truly elementary programming skills I've never used any, beyond basic level, recursion in a program so it was a good illustration of its power... Kinda reminds me of some of the discussions in GEB
Thanks again (I must say, again: truly neat and clever programming),
Marcos
P.S. I was using the "normal method" and trying to expand it for general number of products but the algos I was getting were far too longwinded and complicated (I guess from now on it's "When stuck, ask Arun")...
| Posted on Sunday, 13 July, 2003 - 07:42 pm: |
lol!
love arun
| Posted on Monday, 14 July, 2003 - 08:27 pm: |
Arun (or some other C-programmer),
Can I just ask a question about programming in C since I'm quite new to it (sorry Emma for the non-maths question):
What is the best way to create and manipulate matrices (in the mathematical sense) in functions where you don't know the size of the matrix?
Ultimately, is it possible to make a sort of matrix class where the size of the rectangular array is decided when you declare a matrix object and use matrix classes in functions? (I can't overcome the problem that you need to know the array size of an array in functions before the program is run)
I know that wasn't very clear, sorry
Marcos
| Posted on Wednesday, 16 July, 2003 - 02:53 pm: |
int **matrix,rows,columns;
printf("Enter No. of Rows and Columns:");
scanf("%d %d",&rows,&columns);
matrix = new int*[rows];
for(int i=0;i < rows;i++)
matrix[i]=new int[columns];
the above matrix can be easily accessed as a matrix[i][j].
the above idea can be extended to make a Class Matrix by proper use of constructor.
love arun
| Posted on Wednesday, 16 July, 2003 - 03:58 pm: |
Thanks
Marcos