Mixing
Find a set of size $m$ consisting of vectors from $mathbbR^n$, so that each of its subsets of size $n$ is linearly independent.
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Find a set of size $m$ consisting of vectors from $mathbbR^n$, so that each of its subsets of size $n$ is linearly independent.
Also, what is the maximum $m$ for which this is possible?
So here is my attempt at calculating an upper-bound by induction: $binomn+12$. We can assume $n$ of the vectors are our standard basis. Let the rest of the set be $B$. Now from the standard basis take $varepsilon_1$, this vector and subset of $B$ of size $n-1$ must together form an independent set. Hence $B$ has size at most $binomn2$. Which proves our claim. But I am unable to construct an example with such many vectors or attain a lower upper-bound.
It was pointed out in the comments this proof is wrong, as it doesn't hold for n = 2.
linear-algebra
asked Jul 23 at 22:48
J. Doe
11
add a comment |Â
up vote
0
down vote
favorite
Find a set of size $m$ consisting of vectors from $mathbbR^n$, so that each of its subsets of size $n$ is linearly independent.
Also, what is the maximum $m$ for which this is possible?
So here is my attempt at calculating an upper-bound by induction: $binomn+12$. We can assume $n$ of the vectors are our standard basis. Let the rest of the set be $B$. Now from the standard basis take $varepsilon_1$, this vector and subset of $B$ of size $n-1$ must together form an independent set. Hence $B$ has size at most $binomn2$. Which proves our claim. But I am unable to construct an example with such many vectors or attain a lower upper-bound.
It was pointed out in the comments this proof is wrong, as it doesn't hold for n = 2.
linear-algebra
asked Jul 23 at 22:48
J. Doe
11
5
Consider $Bbb R^2$ and consider the set of vectors $A=left(x,1)~:~xinBbb Rright$. It should be clear that every pair of vectors in $A$ are linearly independent and it should also be clear that $A$ is uncountably infinite in size.
– JMoravitz
Jul 23 at 22:53
@JMoravitz Can you construct such an arbitrarily set for any n?
– J. Doe
Jul 23 at 23:06
1
Yes. Consider the set $A=(1,x,x^2,x^3,dots,x^n-1)~:~xinBbb Rsubseteq Bbb R^n$. Any set of $n$ distinct elements of $A$ will be linearly independent. See Vandermonde Matrix on wikipedia for additional details.
– JMoravitz
Jul 23 at 23:28
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Find a set of size $m$ consisting of vectors from $mathbbR^n$, so that each of its subsets of size $n$ is linearly independent.
Also, what is the maximum $m$ for which this is possible?
So here is my attempt at calculating an upper-bound by induction: $binomn+12$. We can assume $n$ of the vectors are our standard basis. Let the rest of the set be $B$. Now from the standard basis take $varepsilon_1$, this vector and subset of $B$ of size $n-1$ must together form an independent set. Hence $B$ has size at most $binomn2$. Which proves our claim. But I am unable to construct an example with such many vectors or attain a lower upper-bound.
It was pointed out in the comments this proof is wrong, as it doesn't hold for n = 2.
linear-algebra
asked Jul 23 at 22:48
J. Doe
11
Find a set of size $m$ consisting of vectors from $mathbbR^n$, so that each of its subsets of size $n$ is linearly independent.
Also, what is the maximum $m$ for which this is possible?
So here is my attempt at calculating an upper-bound by induction: $binomn+12$. We can assume $n$ of the vectors are our standard basis. Let the rest of the set be $B$. Now from the standard basis take $varepsilon_1$, this vector and subset of $B$ of size $n-1$ must together form an independent set. Hence $B$ has size at most $binomn2$. Which proves our claim. But I am unable to construct an example with such many vectors or attain a lower upper-bound.
It was pointed out in the comments this proof is wrong, as it doesn't hold for n = 2.
linear-algebra
asked Jul 23 at 22:48
J. Doe
11
edited Jul 23 at 23:05
asked Jul 23 at 22:48
J. Doe
11
asked Jul 23 at 22:48
J. Doe
11
asked Jul 23 at 22:48
J. Doe
11
11
5
Consider $Bbb R^2$ and consider the set of vectors $A=left(x,1)~:~xinBbb Rright$. It should be clear that every pair of vectors in $A$ are linearly independent and it should also be clear that $A$ is uncountably infinite in size.
– JMoravitz
Jul 23 at 22:53
@JMoravitz Can you construct such an arbitrarily set for any n?
– J. Doe
Jul 23 at 23:06
1
Yes. Consider the set $A=(1,x,x^2,x^3,dots,x^n-1)~:~xinBbb Rsubseteq Bbb R^n$. Any set of $n$ distinct elements of $A$ will be linearly independent. See Vandermonde Matrix on wikipedia for additional details.
– JMoravitz
Jul 23 at 23:28
add a comment |Â
5
Consider $Bbb R^2$ and consider the set of vectors $A=left(x,1)~:~xinBbb Rright$. It should be clear that every pair of vectors in $A$ are linearly independent and it should also be clear that $A$ is uncountably infinite in size.
– JMoravitz
Jul 23 at 22:53
@JMoravitz Can you construct such an arbitrarily set for any n?
– J. Doe
Jul 23 at 23:06
1
Yes. Consider the set $A=(1,x,x^2,x^3,dots,x^n-1)~:~xinBbb Rsubseteq Bbb R^n$. Any set of $n$ distinct elements of $A$ will be linearly independent. See Vandermonde Matrix on wikipedia for additional details.
– JMoravitz
Jul 23 at 23:28
5
5
Consider $Bbb R^2$ and consider the set of vectors $A=left(x,1)~:~xinBbb Rright$. It should be clear that every pair of vectors in $A$ are linearly independent and it should also be clear that $A$ is uncountably infinite in size.
– JMoravitz
Jul 23 at 22:53
Consider $Bbb R^2$ and consider the set of vectors $A=left(x,1)~:~xinBbb Rright$. It should be clear that every pair of vectors in $A$ are linearly independent and it should also be clear that $A$ is uncountably infinite in size.
– JMoravitz
Jul 23 at 22:53
@JMoravitz Can you construct such an arbitrarily set for any n?
– J. Doe
Jul 23 at 23:06
@JMoravitz Can you construct such an arbitrarily set for any n?
– J. Doe
Jul 23 at 23:06
1
1
Yes. Consider the set $A=(1,x,x^2,x^3,dots,x^n-1)~:~xinBbb Rsubseteq Bbb R^n$. Any set of $n$ distinct elements of $A$ will be linearly independent. See Vandermonde Matrix on wikipedia for additional details.
– JMoravitz
Jul 23 at 23:28
Yes. Consider the set $A=(1,x,x^2,x^3,dots,x^n-1)~:~xinBbb Rsubseteq Bbb R^n$. Any set of $n$ distinct elements of $A$ will be linearly independent. See Vandermonde Matrix on wikipedia for additional details.
– JMoravitz
Jul 23 at 23:28
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
An important example is the so called "moment curve" of points $(1,t,t^2,dots t^n-1)$. If we choose all of our $m$ points to be on this curve, the claim is that any $n$ of them will be linearly independent.
So see this, suppose not, then there would be a linear functional $a_1x_1+a_2x_2+ dots a_nx_n = 0$ satisfied by all of them with out all of the $a_i$'s being $0$. But then the polynomial $a_1+a_2x+a_3x^2+ dots a_nx^n-1$ would be a degree $n-1$ polynomial with $n$ roots, a contradiction.
Of course if you randomly choose $m$ points say uniformly within a ball or from a gaussian distribution they will also have this property you want with probability $1$...
answered Jul 23 at 23:27
Nate
6,57011020
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
An important example is the so called "moment curve" of points $(1,t,t^2,dots t^n-1)$. If we choose all of our $m$ points to be on this curve, the claim is that any $n$ of them will be linearly independent.
So see this, suppose not, then there would be a linear functional $a_1x_1+a_2x_2+ dots a_nx_n = 0$ satisfied by all of them with out all of the $a_i$'s being $0$. But then the polynomial $a_1+a_2x+a_3x^2+ dots a_nx^n-1$ would be a degree $n-1$ polynomial with $n$ roots, a contradiction.
Of course if you randomly choose $m$ points say uniformly within a ball or from a gaussian distribution they will also have this property you want with probability $1$...
answered Jul 23 at 23:27
Nate
6,57011020
add a comment |Â
up vote
1
down vote
An important example is the so called "moment curve" of points $(1,t,t^2,dots t^n-1)$. If we choose all of our $m$ points to be on this curve, the claim is that any $n$ of them will be linearly independent.
So see this, suppose not, then there would be a linear functional $a_1x_1+a_2x_2+ dots a_nx_n = 0$ satisfied by all of them with out all of the $a_i$'s being $0$. But then the polynomial $a_1+a_2x+a_3x^2+ dots a_nx^n-1$ would be a degree $n-1$ polynomial with $n$ roots, a contradiction.
Of course if you randomly choose $m$ points say uniformly within a ball or from a gaussian distribution they will also have this property you want with probability $1$...
answered Jul 23 at 23:27
Nate
6,57011020
add a comment |Â
up vote
1
down vote
up vote
1
down vote
An important example is the so called "moment curve" of points $(1,t,t^2,dots t^n-1)$. If we choose all of our $m$ points to be on this curve, the claim is that any $n$ of them will be linearly independent.
So see this, suppose not, then there would be a linear functional $a_1x_1+a_2x_2+ dots a_nx_n = 0$ satisfied by all of them with out all of the $a_i$'s being $0$. But then the polynomial $a_1+a_2x+a_3x^2+ dots a_nx^n-1$ would be a degree $n-1$ polynomial with $n$ roots, a contradiction.
Of course if you randomly choose $m$ points say uniformly within a ball or from a gaussian distribution they will also have this property you want with probability $1$...
answered Jul 23 at 23:27
Nate
6,57011020
An important example is the so called "moment curve" of points $(1,t,t^2,dots t^n-1)$. If we choose all of our $m$ points to be on this curve, the claim is that any $n$ of them will be linearly independent.
So see this, suppose not, then there would be a linear functional $a_1x_1+a_2x_2+ dots a_nx_n = 0$ satisfied by all of them with out all of the $a_i$'s being $0$. But then the polynomial $a_1+a_2x+a_3x^2+ dots a_nx^n-1$ would be a degree $n-1$ polynomial with $n$ roots, a contradiction.
Of course if you randomly choose $m$ points say uniformly within a ball or from a gaussian distribution they will also have this property you want with probability $1$...
answered Jul 23 at 23:27
Nate
6,57011020
answered Jul 23 at 23:27
Nate
6,57011020
answered Jul 23 at 23:27
Nate
6,57011020
answered Jul 23 at 23:27
Nate
6,57011020
6,57011020
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2860842%2ffind-a-set-of-size-m-consisting-of-vectors-from-mathbbrn-so-that-each-o%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
5
Consider $Bbb R^2$ and consider the set of vectors $A=left(x,1)~:~xinBbb Rright$. It should be clear that every pair of vectors in $A$ are linearly independent and it should also be clear that $A$ is uncountably infinite in size.
– JMoravitz
Jul 23 at 22:53
@JMoravitz Can you construct such an arbitrarily set for any n?
– J. Doe
Jul 23 at 23:06
1
Yes. Consider the set $A=(1,x,x^2,x^3,dots,x^n-1)~:~xinBbb Rsubseteq Bbb R^n$. Any set of $n$ distinct elements of $A$ will be linearly independent. See Vandermonde Matrix on wikipedia for additional details.
– JMoravitz
Jul 23 at 23:28