vandermonde matrix question
SportsNut
by T(f)=(f(c_o), f(c_1), ... , f(c_n)), where
c_o, c_1, ..., c_n are distinct scalars in the infinite
field F. Let B be the standard ordered basis for P_n(F)
and y be the standard ordered basis for F^(n+1).
1) How can I show that M=[T]y,B has the form:
[1 c_o (c_o)^2 ... (c_o)^n
1 c_1 (c_1)^2 ... (c_1)^n
.
.
.
1 c_n (c_n)^2 ... (c_n)^n]
2) How can I use the fact that I know that T is an
isomorphism to prove that det(M)=/0? (doesn't equal 0)
3) How can I show that det(M)= [product] ((c_j)-(c_i))?
Thanks!
Gerry Myerson
<27556868.1130962933...@nitrogen.mathforum.org>,
SportsNut <ds...@gmail.com> wrote:
> Let T: P_n(F)->F^(n+1) be the linear transformation defined
> by T(f)=(f(c_o), f(c_1), ... , f(c_n)), where
> c_o, c_1, ..., c_n are distinct scalars in the infinite
> field F. Let B be the standard ordered basis for P_n(F)
> and y be the standard ordered basis for F^(n+1).
>
> 1) How can I show that M=[T]y,B has the form:
> [1 c_o (c_o)^2 ... (c_o)^n
> 1 c_1 (c_1)^2 ... (c_1)^n
> .
> .
> .
> 1 c_n (c_n)^2 ... (c_n)^n]
I take it [T]y,B is notation for the matrix representing T
with respect to the bases y and B.
You say B is the standard ordered basis for P_n(F) - do you know
what this means?
You say y is the standard ordered basis for F^(n+1) - do you know
what this means?
Do you know how to find the matrix representing a linear
transformation?
> 2) How can I use the fact that I know that T is an
> isomorphism to prove that det(M)=/0? (doesn't equal 0)
Do you know what an isomorphism is? Do you know what you can say
about a matrix if its determinant is not zero?
> 3) How can I show that det(M)= [product] ((c_j)-(c_i))?
Now this is the only part of the problem that isn't trivial
for someone who actually understands the definitions of the terms
in the problem. Even so, if you know about the effects of row
and column operations on determinants you might be able to put
a proof together, especially if you keep one eye on the goal.
--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
SportsNut
> by T(f)=(f(c_o), f(c_1), ... , f(c_n)), where
> c_o, c_1, ..., c_n are distinct scalars in the infinite
> field F. Let B be the standard ordered basis for P_n(F)
> and y be the standard ordered basis for F^(n+1).
>
> 1) How can I show that M=[T]y,B has the form:
> [1 c_o (c_o)^2 ... (c_o)^n
> 1 c_1 (c_1)^2 ... (c_1)^n
> .
> .
> .
> 1 c_n (c_n)^2 ... (c_n)^n]
I take it [T]y,B is notation for the matrix representing T
with respect to the bases y and B.
You say B is the standard ordered basis for P_n(F) - do you know
what this means?
You say y is the standard ordered basis for F^(n+1) - do you know
what this means?
Do you know how to find the matrix representing a linear
transformation?
A transformation is linear if T(cx+y)= cT(x)+ T(y).
But I am not sure how to show this in this case.
> 2) How can I use the fact that I know that T is an
> isomorphism to prove that det(M)=/0? (doesn't equal 0)
Do you know what an isomorphism is? Do you know what you can say
about a matrix if its determinant is not zero?
If the det(M)=/0, then that matrix is invertible, if it
is square, which it is in this case.
> 3) How can I show that det(M)= [product] ((c_j)-(c_i))?
Now this is the only part of the problem that isn't trivial
for someone who actually understands the definitions of the terms
in the problem. Even so, if you know about the effects of row
and column operations on determinants you might be able to put
a proof together, especially if you keep one eye on the goal.
If I change the row order, does the determinant change?
I am not sure how changing the rows would change anything...
I would think that I should perform row operations on
this matrix, hoping to arise at an upper triangular
matrix, and having the determinant be determined by
the entries on the diagonal...
Gerry Myerson
<23208101.1130990093...@nitrogen.mathforum.org>,
SportsNut <ds...@gmail.com> wrote:
>> > Let T: P_n(F)->F^(n+1) be the linear transformation defined
>> > by T(f)=(f(c_o), f(c_1), ... , f(c_n)), where
>> > c_o, c_1, ..., c_n are distinct scalars in the infinite
>> > field F. Let B be the standard ordered basis for P_n(F)
>> > and y be the standard ordered basis for F^(n+1).
>> >
>> > 1) How can I show that M=[T]y,B has the form:
>> > [1 c_o (c_o)^2 ... (c_o)^n
>> > 1 c_1 (c_1)^2 ... (c_1)^n
>> > .
>> > .
>> > .
>> > 1 c_n (c_n)^2 ... (c_n)^n]
>>
>> I take it [T]y,B is notation for the matrix representing T
>> with respect to the bases y and B.
>>
>> You say B is the standard ordered basis for P_n(F) - do you know
>> what this means?
>>
>> You say y is the standard ordered basis for F^(n+1) - do you know
>> what this means?
>>
>> Do you know how to find the matrix representing a linear
>> transformation?
>
> A transformation is linear if T(cx+y)= cT(x)+ T(y).
> But I am not sure how to show this in this case.
A transformation is linear if T(c x + y) = c T(x) + T(y)
for all c in F and all x and y in the domain, but it is
neither necessary nor helpful to show that the given
transformation is linear. The statement of the problem
says that the transformation is linear.
In any event, you didn't answer any of my questions.
If you don't know the answers, say so - you don't have a prayer
of solving the problem if you can't answer my questions, so
that way we'll know where we have to start.
>> > 2) How can I use the fact that I know that T is an
>> > isomorphism to prove that det(M)=/0? (doesn't equal 0)
>>
>> Do you know what an isomorphism is? Do you know what you can say
>> about a matrix if its determinant is not zero?
>
> If the det(M)=/0, then that matrix is invertible, if it
> is square, which it is in this case.
Yes, that's good. But what about the other question - do you know
what an isomorphism is, in particular what distinguishes an
isomorphism from any other kind of linear transformation? If not,
say so - you have no hope of doing the problem until you find out.
>> > 3) How can I show that det(M)= [product] ((c_j)-(c_i))?
>>
>> Now this is the only part of the problem that isn't trivial
>> for someone who actually understands the definitions of the terms
>> in the problem. Even so, if you know about the effects of row
>> and column operations on determinants you might be able to put
>> a proof together, especially if you keep one eye on the goal.
>
> If I change the row order, does the determinant change?
> I am not sure how changing the rows would change anything...
>
> I would think that I should perform row operations on
> this matrix, hoping to arise at an upper triangular
> matrix, and having the determinant be determined by
> the entries on the diagonal...
Sounds good - but be sure to do row operations that result in
things like c_j - c_i showing up, so you have a shot at getting
the intended answer.
SportsNut
I am sorry, but I don't know the answers to your questions
in 1) and 2). Can you help? And show their applicability
to this problem at hand?
Also, will this matrix be able to be row reduced into
an triangular matrix? I would like to think so, but
would feel like a fool if I sat row reducing all this
and it failed to even come out clean...
Gerry Myerson
<4813187.11310515709...@nitrogen.mathforum.org>,
SportsNut <ds...@gmail.com> wrote:
<The previous posts included were getting a bit out of hand,
so I've snipped them.>
> I am sorry, but I don't know the answers to your questions
> in 1) and 2). Can you help? And show their applicability
> to this problem at hand?
OK, so you don't know the standard ordered basis for P_n(F),
so I'll tell you what it is: it is 1, x, x^2, ..., x^n.
I do hope you understand what P_n(F) is, and what a basis
for a vector space is, and why the list I've given is indeed
a basis for P_n(F). If you don't, then the problem we are
discussing is way too difficult for you - you have to go back
to Chapter Zero of some linear algebra text & start reading.
You don't know what the standard ordered basis for F^(n+1) is,
so I'll tell you: it's (1,0,...,0), (0,1,0,...,0), ...,
(0,0,...,0,1). I hope you understand what F^(n+1) is, and why
the list I've given is a basis for F^(n+1). If you don't, then
the problem we are discussing is way too difficult for you -
you have to go back to Chapter Zero of some linear algebra text
and start reading.
Now, you don't know how to find the matrix representing a linear
transformation, so I'll tell you. Suppose you've got a linear
transformation T from a vector space V to a vector space W, and
suppose you've got a basis b_1, ..., b_m for V, and a basis
c_1, ..., c_n for W. Then for each j between 1 and m, T(b_j)
is an element of W, so it is a linear combination of the basis
vectors for W; say, T(b_j)=a_1j c_1 + a_2j c_2 + ... + a_nj c_n,
where the a_ij are elements of F. Then the matrix you're looking
for is the matrix whose entry in row i, column j, is a_ij.
Now see if you can do the 1st problem. If not, you've probably
bitten off more than you can chew - go back to Square One.
> Also, will this matrix be able to be row reduced into
> an triangular matrix? I would like to think so, but
> would feel like a fool if I sat row reducing all this
> and it failed to even come out clean...
Every matrix can be row-reduced to a triangular matrix.
Ed Hook
SportsNut wrote:
> Let T: P_n(F)->F^(n+1) be the linear transformation defined
> by T(f)=(f(c_o), f(c_1), ... , f(c_n)), where
> c_o, c_1, ..., c_n are distinct scalars in the infinite
> field F. Let B be the standard ordered basis for P_n(F)
> and y be the standard ordered basis for F^(n+1).
>
> 1) How can I show that M=[T]y,B has the form:
> [1 c_o (c_o)^2 ... (c_o)^n
> 1 c_1 (c_1)^2 ... (c_1)^n
> .
> .
> .
> 1 c_n (c_n)^2 ... (c_n)^n]
>
>
> 2) How can I use the fact that I know that T is an
> isomorphism to prove that det(M)=/0? (doesn't equal 0)
>
Gerry Myerson is already well-launched on answering these
questions, but (since it's Saturday morning and I've got some
work to avoid doing ...) I'd like to contribute the following:
> 3) How can I show that det(M)= [product] ((c_j)-(c_i))?
... more precisely, det(M) = product_{0<= i < j <= n} (c_j - c_i).
Here's an approach that avoid some of the messy bookkeeping
that's required for a direct proof:
Let V_n(c_0,c_1,...,c_n) denote the determinant in question, where
we assume that the c_k's are distinct _and_ that all are nonzero
except possibly c_n. Consider the polynomial p in F[x] defined by
p(x) = V_n(c_0,c_1,...,c_{n-1},x) .
It is immediate from elementary properties of determinants that
p(c_0) = p(c_1) = ... = p(c_{n-1}) = 0 ,
so we conclude that
p(x) = K_n Product (x - c_i)
i < n
for some constant K_n. It just remains to evaluate K_n and, for that
purpose, we "compute" p(0). This is the determinant of a matrix
whose
last row consists of a 1 followed by n 0s and it fairly screams out
to be
evaluated by expansion using the cofactors of that last row. This
gives
[ c_0 (c_0)^2 ...
(c_0)^n ]
p(0) = (-1)^{n+2} det [ .
] ;
.
[ c_{n-1} (c_{n-1})^2 ...
(c_{n-1})^n ]
Now, take a factor of c_k out of row k+1 for each k (here's where
we
use the assumption that none of c_0, ... , c_{n-1} is 0) to obtain
the
result that
p(0) = (-1)^{n+2} c_0 c_1 ... c_{n-1}
V_{n-1}(c_0,...,c_{n-1})
or (finally) that K_n = V_{n-1}(c_0,...,c_{n-1}). Hence,
p(x) = V_(n-1}(c_0,...,c_{n-1}) Product (x - c_i)
i < n
and plugging in c_n for x yields
V_n(c_0,...,c_{n-1},c_n) = V_{n-1}(c_0,...,c_{n-1}) Product
(c_n - c_i) .
i < n
Since (obviously) V_1(c_0,c_1) = c_1 - c_0, the desired result
follows
by induction.
> Thanks!
Bill Dubuque
>> c_o, c_1, ..., c_n are distinct scalars in the infinite
>> field F. Let B be the standard ordered basis for P_n(F)
>> and y be the standard ordered basis for F^(n+1).
>>
>>
>> [ 1 c_o (c_o)^2 ... (c_o)^n
>> 1 c_1 (c_1)^2 ... (c_1)^n
>> .
>> .
>> .
>> 1 c_n (c_n)^2 ... (c_n)^n ]
>>
>
> Let V_n(c_0,c_1,...,c_n) denote the determinant in question, where
> except possibly c_n.
Why impose such unnatural restrictions on the c_i? V_n is clearly a
polynomial in the c_i so cannot possibly possess such singularities.
> Consider the polynomial p in F[x] defined by
>
> p(x) = V_n(c_0,c_1,...,c_{n-1},x) .
>
> It is immediate from elementary properties of determinants that
>
> p(c_0) = p(c_1) = ... = p(c_{n-1}) = 0 ,
>
> so we conclude that
> p(x) = K_n Product (x - c_i)
> i < n
Here's the problem. One should be working over Z[c_i] not K[x],
i.e. one should by treating *all* of the c_i as indeterminates,
i.e. working "universally". For more on this see my prior post [1].
In particular, be sure to understand why this universal approach
eliminates the unnatural restrictions imposed above.
> for some constant K_n. It just remains to evaluate K_n and, for that
> purpose, we "compute" p(0). This is the determinant of a matrix whose
That's the hard way. Instead one should simply note that the coef of x^n
(or c_n^n) is simply V_{n-1}, by considering expansion on the last row.
Equivalently: interpolate V_n at the points c_i and oo (vs. 0).
I discussed this here a couple weeks ago [2].
> last row consists of a 1 followed by n 0s and it fairly screams out to be
> evaluated by expansion using the cofactors of that last row. This gives
>
> [ c_0 (c_0)^2 ... (c_0)^n ]
> . .
> p(0) = (-1)^{n+2} det [ . . ] ;
> . . .
> [ c_{n-1} (c_{n-1})^2 ... (c_{n-1})^n ]
>
> Now, take a factor of c_k out of row k+1 for each k (here's where we
> use the assumption that none of c_0, ... , c_{n-1} is 0) to obtain
>
> p(0) = (-1)^{n+2} c_0 c_1 ... c_{n-1} V_{n-1}(c_0,...,c_{n-1})
>
> or (finally) that K_n = V_{n-1}(c_0,...,c_{n-1}). Hence,
>
> p(x) = V_{n-1}(c_0,...,c_{n-1}) Product (x - c_i)
> i < n
> and plugging in c_n for x yields
>
> V_n(c_0,...,c_{n-1},c_n) = V_{n-1}(c_0,...,c_{n-1}) Product (c_n - c_i) .
> i < n
>
> Since V_1(c_0,c_1) = c_1 - c_0, the desired result follows by induction.
--Bill Dubuque
[1] http://google.com/groups?selm=y8zznru8v1d.fsf%40nestle.ai.mit.edu
[2] http://google.com/groups?selm=y8zk6g65shf.fsf%40nestle.csail.mit.edu
Bill Dubuque
the Vandermonde determinant see
--------------------------------------------------------------------------
2002i:05013 05A19 (15A15 33C99)
Krattenthaler, C. (A-WIEN)
Advanced determinant calculus.
The Andrews Festschrift (Maratea, 1998).
Sem. Lothar. Combin. 42 (1999), Art. B42q, 67 pp. (electronic).
http://www.mat.univie.ac.at/~slc/wpapers/s42kratt.html
--------------------------------------------------------------------------
This paper is an excellent survey of methods used in the evaluation of what
the author calls "non-trivial determinants". It is important to distinguish
the content of this paper from the equally important but quite different
problems that arise in the numerical evaluation of determinants with purely
numerical entries.
The paper under review is primarily interested in closed form evaluation of
sequences of determinants {A_n, n = 1,2,...} wherein A_n is an n x n
determinant. The classical Vandermonde determinant is a prototypical example.
The introduction to the paper provides a succinct history of the topic.
Section 2 is devoted to an account of the methods for doing these
evaluations. It should be noted that the author has done more than anyone
in the development of these effective procedures. Section 3 then presents
an extensive list of many of the evaluations that have been obtained by
the methods of Section 2.
It should be stressed that this is a valuable, useful and unique survey
carefully prepared by the only person who could successfully pull it all
together.
Reviewed by George E. Andrews
--Bill Dubuque