how do I check linear independence of m vectors, given the m-1 first vectors are independence?
$begingroup$
I have a set of m-1 vectors of size n, they are independence. I want to add another vector and to check if the m vectors are still independence. It is known m < n. I am looking for a good algorithm & running time.
Thanks
linear-algebra algorithms
asked Jan 20 at 9:15
ShaqShaq
2849
$endgroup$
add a comment |
$begingroup$
I have a set of m-1 vectors of size n, they are independence. I want to add another vector and to check if the m vectors are still independence. It is known m < n. I am looking for a good algorithm & running time.
Thanks
linear-algebra algorithms
asked Jan 20 at 9:15
ShaqShaq
2849
$endgroup$
$begingroup$
I guess you want to use the linear independence of the $ m-1 $ vectors for a shortcut. Is that right ?
$endgroup$
– Peter
Jan 20 at 9:44
$begingroup$
nope, just it is greater the the number of vectors you have, so you cannot negate it directly.. and yes this is what I am looking for
$endgroup$
– Shaq
Jan 20 at 9:46
$begingroup$
Then, determining the rank (as mentioned in my answer) should be a suitable approach.
$endgroup$
– Peter
Jan 20 at 9:48
add a comment |
$begingroup$
I have a set of m-1 vectors of size n, they are independence. I want to add another vector and to check if the m vectors are still independence. It is known m < n. I am looking for a good algorithm & running time.
Thanks
linear-algebra algorithms
asked Jan 20 at 9:15
ShaqShaq
2849
$endgroup$
I have a set of m-1 vectors of size n, they are independence. I want to add another vector and to check if the m vectors are still independence. It is known m < n. I am looking for a good algorithm & running time.
Thanks
linear-algebra algorithms
linear-algebra algorithms
asked Jan 20 at 9:15
ShaqShaq
2849
asked Jan 20 at 9:15
ShaqShaq
2849
asked Jan 20 at 9:15
ShaqShaq
2849
asked Jan 20 at 9:15
ShaqShaq
2849
asked Jan 20 at 9:15
ShaqShaq
2849
2849
$begingroup$
I guess you want to use the linear independence of the $ m-1 $ vectors for a shortcut. Is that right ?
$endgroup$
– Peter
Jan 20 at 9:44
$begingroup$
nope, just it is greater the the number of vectors you have, so you cannot negate it directly.. and yes this is what I am looking for
$endgroup$
– Shaq
Jan 20 at 9:46
$begingroup$
Then, determining the rank (as mentioned in my answer) should be a suitable approach.
$endgroup$
– Peter
Jan 20 at 9:48
add a comment |
$begingroup$
I guess you want to use the linear independence of the $ m-1 $ vectors for a shortcut. Is that right ?
$endgroup$
– Peter
Jan 20 at 9:44
$begingroup$
nope, just it is greater the the number of vectors you have, so you cannot negate it directly.. and yes this is what I am looking for
$endgroup$
– Shaq
Jan 20 at 9:46
$begingroup$
Then, determining the rank (as mentioned in my answer) should be a suitable approach.
$endgroup$
– Peter
Jan 20 at 9:48
$begingroup$
I guess you want to use the linear independence of the $ m-1 $ vectors for a shortcut. Is that right ?
$endgroup$
– Peter
Jan 20 at 9:44
$begingroup$
I guess you want to use the linear independence of the $ m-1 $ vectors for a shortcut. Is that right ?
$endgroup$
– Peter
Jan 20 at 9:44
$begingroup$
nope, just it is greater the the number of vectors you have, so you cannot negate it directly.. and yes this is what I am looking for
$endgroup$
– Shaq
Jan 20 at 9:46
$begingroup$
nope, just it is greater the the number of vectors you have, so you cannot negate it directly.. and yes this is what I am looking for
$endgroup$
– Shaq
Jan 20 at 9:46
$begingroup$
Then, determining the rank (as mentioned in my answer) should be a suitable approach.
$endgroup$
– Peter
Jan 20 at 9:48
$begingroup$
Then, determining the rank (as mentioned in my answer) should be a suitable approach.
$endgroup$
– Peter
Jan 20 at 9:48
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
You can use the following criterion :
If you have $ m-1 $ linear independent vectors, then adding the $ m $- th vector gives again a linear independent set if and only if the $ m $ - th vector is not a linear-combination of the original $ m-1 $ vectors, in other words there are no real numbers $ a_1,cdots, a_{m-1} $ with $$sum_{j=1}^{m-1} a_jv_j=v_m$$
For the check I suggest to collect the vectors in a matrix and determine the rank.
answered Jan 20 at 9:24
PeterPeter
47.6k1039131
$endgroup$
$begingroup$
How does this help for checking?
$endgroup$
– mathreadler
Jan 20 at 9:31
1
$begingroup$
@mathreadler It hints at setting up a matrix equation which can be used as a check, at least that's what I gathered.
$endgroup$
– E-mu
Jan 20 at 9:33
$begingroup$
Sure it may hint but then maybe it can be good to at least write hint.
$endgroup$
– mathreadler
Jan 20 at 9:36
$begingroup$
Thanks, I got the theory. I am asking how to do it, I mean how do you check it? What kind of algorithm and hat would be the run time complexity?
$endgroup$
– Shaq
Jan 20 at 9:37
1
$begingroup$
@ShaharMazia I did a bit of searching online, from what I can see it looks like setting up a matrix equation and solving it using the Gaussian elimination algorithm is your best bet, other than randomised algorithms. See mathoverflow.net/questions/6194/….
$endgroup$
– E-mu
Jan 20 at 10:23
add a comment |
$begingroup$
Project the new vector on the others and remove.
If anything remains afterwards then they are linearly independent.
answered Jan 20 at 9:30
mathreadlermathreadler
14.9k72262
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3080352%2fhow-do-i-check-linear-independence-of-m-vectors-given-the-m-1-first-vectors-are%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You can use the following criterion :
If you have $ m-1 $ linear independent vectors, then adding the $ m $- th vector gives again a linear independent set if and only if the $ m $ - th vector is not a linear-combination of the original $ m-1 $ vectors, in other words there are no real numbers $ a_1,cdots, a_{m-1} $ with $$sum_{j=1}^{m-1} a_jv_j=v_m$$
For the check I suggest to collect the vectors in a matrix and determine the rank.
answered Jan 20 at 9:24
PeterPeter
47.6k1039131
$endgroup$
$begingroup$
How does this help for checking?
$endgroup$
– mathreadler
Jan 20 at 9:31
1
$begingroup$
@mathreadler It hints at setting up a matrix equation which can be used as a check, at least that's what I gathered.
$endgroup$
– E-mu
Jan 20 at 9:33
$begingroup$
Sure it may hint but then maybe it can be good to at least write hint.
$endgroup$
– mathreadler
Jan 20 at 9:36
$begingroup$
Thanks, I got the theory. I am asking how to do it, I mean how do you check it? What kind of algorithm and hat would be the run time complexity?
$endgroup$
– Shaq
Jan 20 at 9:37
1
$begingroup$
@ShaharMazia I did a bit of searching online, from what I can see it looks like setting up a matrix equation and solving it using the Gaussian elimination algorithm is your best bet, other than randomised algorithms. See mathoverflow.net/questions/6194/….
$endgroup$
– E-mu
Jan 20 at 10:23
add a comment |
$begingroup$
You can use the following criterion :
If you have $ m-1 $ linear independent vectors, then adding the $ m $- th vector gives again a linear independent set if and only if the $ m $ - th vector is not a linear-combination of the original $ m-1 $ vectors, in other words there are no real numbers $ a_1,cdots, a_{m-1} $ with $$sum_{j=1}^{m-1} a_jv_j=v_m$$
For the check I suggest to collect the vectors in a matrix and determine the rank.
answered Jan 20 at 9:24
PeterPeter
47.6k1039131
$endgroup$
$begingroup$
How does this help for checking?
$endgroup$
– mathreadler
Jan 20 at 9:31
1
$begingroup$
@mathreadler It hints at setting up a matrix equation which can be used as a check, at least that's what I gathered.
$endgroup$
– E-mu
Jan 20 at 9:33
$begingroup$
Sure it may hint but then maybe it can be good to at least write hint.
$endgroup$
– mathreadler
Jan 20 at 9:36
$begingroup$
Thanks, I got the theory. I am asking how to do it, I mean how do you check it? What kind of algorithm and hat would be the run time complexity?
$endgroup$
– Shaq
Jan 20 at 9:37
1
$begingroup$
@ShaharMazia I did a bit of searching online, from what I can see it looks like setting up a matrix equation and solving it using the Gaussian elimination algorithm is your best bet, other than randomised algorithms. See mathoverflow.net/questions/6194/….
$endgroup$
– E-mu
Jan 20 at 10:23
add a comment |
$begingroup$
You can use the following criterion :
If you have $ m-1 $ linear independent vectors, then adding the $ m $- th vector gives again a linear independent set if and only if the $ m $ - th vector is not a linear-combination of the original $ m-1 $ vectors, in other words there are no real numbers $ a_1,cdots, a_{m-1} $ with $$sum_{j=1}^{m-1} a_jv_j=v_m$$
For the check I suggest to collect the vectors in a matrix and determine the rank.
answered Jan 20 at 9:24
PeterPeter
47.6k1039131
$endgroup$
You can use the following criterion :
If you have $ m-1 $ linear independent vectors, then adding the $ m $- th vector gives again a linear independent set if and only if the $ m $ - th vector is not a linear-combination of the original $ m-1 $ vectors, in other words there are no real numbers $ a_1,cdots, a_{m-1} $ with $$sum_{j=1}^{m-1} a_jv_j=v_m$$
For the check I suggest to collect the vectors in a matrix and determine the rank.
answered Jan 20 at 9:24
PeterPeter
47.6k1039131
edited Jan 20 at 9:38
answered Jan 20 at 9:24
PeterPeter
47.6k1039131
answered Jan 20 at 9:24
PeterPeter
47.6k1039131
answered Jan 20 at 9:24
PeterPeter
47.6k1039131
47.6k1039131
$begingroup$
How does this help for checking?
$endgroup$
– mathreadler
Jan 20 at 9:31
1
$begingroup$
@mathreadler It hints at setting up a matrix equation which can be used as a check, at least that's what I gathered.
$endgroup$
– E-mu
Jan 20 at 9:33
$begingroup$
Sure it may hint but then maybe it can be good to at least write hint.
$endgroup$
– mathreadler
Jan 20 at 9:36
$begingroup$
Thanks, I got the theory. I am asking how to do it, I mean how do you check it? What kind of algorithm and hat would be the run time complexity?
$endgroup$
– Shaq
Jan 20 at 9:37
1
$begingroup$
@ShaharMazia I did a bit of searching online, from what I can see it looks like setting up a matrix equation and solving it using the Gaussian elimination algorithm is your best bet, other than randomised algorithms. See mathoverflow.net/questions/6194/….
$endgroup$
– E-mu
Jan 20 at 10:23
add a comment |
$begingroup$
How does this help for checking?
$endgroup$
– mathreadler
Jan 20 at 9:31
1
$begingroup$
@mathreadler It hints at setting up a matrix equation which can be used as a check, at least that's what I gathered.
$endgroup$
– E-mu
Jan 20 at 9:33
$begingroup$
Sure it may hint but then maybe it can be good to at least write hint.
$endgroup$
– mathreadler
Jan 20 at 9:36
$begingroup$
Thanks, I got the theory. I am asking how to do it, I mean how do you check it? What kind of algorithm and hat would be the run time complexity?
$endgroup$
– Shaq
Jan 20 at 9:37
1
$begingroup$
@ShaharMazia I did a bit of searching online, from what I can see it looks like setting up a matrix equation and solving it using the Gaussian elimination algorithm is your best bet, other than randomised algorithms. See mathoverflow.net/questions/6194/….
$endgroup$
– E-mu
Jan 20 at 10:23
$begingroup$
How does this help for checking?
$endgroup$
– mathreadler
Jan 20 at 9:31
$begingroup$
How does this help for checking?
$endgroup$
– mathreadler
Jan 20 at 9:31
1
1
$begingroup$
@mathreadler It hints at setting up a matrix equation which can be used as a check, at least that's what I gathered.
$endgroup$
– E-mu
Jan 20 at 9:33
$begingroup$
@mathreadler It hints at setting up a matrix equation which can be used as a check, at least that's what I gathered.
$endgroup$
– E-mu
Jan 20 at 9:33
$begingroup$
Sure it may hint but then maybe it can be good to at least write hint.
$endgroup$
– mathreadler
Jan 20 at 9:36
$begingroup$
Sure it may hint but then maybe it can be good to at least write hint.
$endgroup$
– mathreadler
Jan 20 at 9:36
$begingroup$
Thanks, I got the theory. I am asking how to do it, I mean how do you check it? What kind of algorithm and hat would be the run time complexity?
$endgroup$
– Shaq
Jan 20 at 9:37
$begingroup$
Thanks, I got the theory. I am asking how to do it, I mean how do you check it? What kind of algorithm and hat would be the run time complexity?
$endgroup$
– Shaq
Jan 20 at 9:37
1
1
$begingroup$
@ShaharMazia I did a bit of searching online, from what I can see it looks like setting up a matrix equation and solving it using the Gaussian elimination algorithm is your best bet, other than randomised algorithms. See mathoverflow.net/questions/6194/….
$endgroup$
– E-mu
Jan 20 at 10:23
$begingroup$
@ShaharMazia I did a bit of searching online, from what I can see it looks like setting up a matrix equation and solving it using the Gaussian elimination algorithm is your best bet, other than randomised algorithms. See mathoverflow.net/questions/6194/….
$endgroup$
– E-mu
Jan 20 at 10:23
add a comment |
$begingroup$
Project the new vector on the others and remove.
If anything remains afterwards then they are linearly independent.
answered Jan 20 at 9:30
mathreadlermathreadler
14.9k72262
$endgroup$
add a comment |
$begingroup$
Project the new vector on the others and remove.
If anything remains afterwards then they are linearly independent.
answered Jan 20 at 9:30
mathreadlermathreadler
14.9k72262
$endgroup$
add a comment |
$begingroup$
Project the new vector on the others and remove.
If anything remains afterwards then they are linearly independent.
answered Jan 20 at 9:30
mathreadlermathreadler
14.9k72262
$endgroup$
Project the new vector on the others and remove.
If anything remains afterwards then they are linearly independent.
answered Jan 20 at 9:30
mathreadlermathreadler
14.9k72262
answered Jan 20 at 9:30
mathreadlermathreadler
14.9k72262
answered Jan 20 at 9:30
mathreadlermathreadler
14.9k72262
answered Jan 20 at 9:30
mathreadlermathreadler
14.9k72262
14.9k72262
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3080352%2fhow-do-i-check-linear-independence-of-m-vectors-given-the-m-1-first-vectors-are%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
I guess you want to use the linear independence of the $ m-1 $ vectors for a shortcut. Is that right ?
$endgroup$
– Peter
Jan 20 at 9:44
$begingroup$
nope, just it is greater the the number of vectors you have, so you cannot negate it directly.. and yes this is what I am looking for
$endgroup$
– Shaq
Jan 20 at 9:46
$begingroup$
Then, determining the rank (as mentioned in my answer) should be a suitable approach.
$endgroup$
– Peter
Jan 20 at 9:48