Probability of linear independency of vectors under finite field
0
$begingroup$
How can I compute the probability of linear independency of m vectors under finite field? The vectors length assumed to be equal to n and vector elements to be random uniformly distributed. Thank you very much.
linear-algebra combinatorics finite-fields
asked Dec 12 '18 at 15:40
Treasure BTreasure B
133
$endgroup$
add a comment |
0
$begingroup$
How can I compute the probability of linear independency of m vectors under finite field? The vectors length assumed to be equal to n and vector elements to be random uniformly distributed. Thank you very much.
linear-algebra combinatorics finite-fields
asked Dec 12 '18 at 15:40
Treasure BTreasure B
133
$endgroup$
$begingroup$
Start by considering the choice of the first vector. If it is zero, then the second vector is not independent. So it becomes a counting problem, how many selections of $m$ linearly independent vectors can be formed.
$endgroup$
– hardmath
Dec 12 '18 at 15:43
$begingroup$
@hardmath "how many selections of m linearly independent vectors can be formed". Excuse me, I don't understand this. I'd like to check independency of all m vectors. I need it for getting probability that rank of matrix with these vectors is m.
$endgroup$
– Treasure B
Dec 12 '18 at 16:00
2
$begingroup$
This is just a counting exercise. You are to calculate the number of ways of selecting $m$ vectors such that they form the rows of a full rank matrix. Observe that the full rank condition is violated if and only if at some point the next vector is a linear combination of the preceding ones. How many choices does that leave for the first vector? How many for the second? At each point it is easier to calculate the number of vectors in violation. Observe that each point you can assume the earlier picks to be linearly independent (because otherwise you are already guaranteed to fail).
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 16:10
1
$begingroup$
Essentially this is a duplicate of this. I won't cast the first vote because A) the case is not 100% clear cut, B) my vote would be binding because of my dupehammer privilege.
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 16:13
1
$begingroup$
An important aspect of the problem setup is left out, namely the size of the finite field from which the vector entries are drawn. That must be a power of a prime, so $q=p^k$ will serve the purpose. Proceed to count the ways to choose the first vector, and continue by induction.
$endgroup$
– hardmath
Dec 12 '18 at 22:17
add a comment |
0
0
0
$begingroup$
How can I compute the probability of linear independency of m vectors under finite field? The vectors length assumed to be equal to n and vector elements to be random uniformly distributed. Thank you very much.
linear-algebra combinatorics finite-fields
asked Dec 12 '18 at 15:40
Treasure BTreasure B
133
$endgroup$
How can I compute the probability of linear independency of m vectors under finite field? The vectors length assumed to be equal to n and vector elements to be random uniformly distributed. Thank you very much.
linear-algebra combinatorics finite-fields
linear-algebra combinatorics finite-fields
asked Dec 12 '18 at 15:40
Treasure BTreasure B
133
asked Dec 12 '18 at 15:40
Treasure BTreasure B
133
asked Dec 12 '18 at 15:40
Treasure BTreasure B
133
asked Dec 12 '18 at 15:40
Treasure BTreasure B
133
asked Dec 12 '18 at 15:40
Treasure BTreasure B
133
133
$begingroup$
Start by considering the choice of the first vector. If it is zero, then the second vector is not independent. So it becomes a counting problem, how many selections of $m$ linearly independent vectors can be formed.
$endgroup$
– hardmath
Dec 12 '18 at 15:43
$begingroup$
@hardmath "how many selections of m linearly independent vectors can be formed". Excuse me, I don't understand this. I'd like to check independency of all m vectors. I need it for getting probability that rank of matrix with these vectors is m.
$endgroup$
– Treasure B
Dec 12 '18 at 16:00
2
$begingroup$
This is just a counting exercise. You are to calculate the number of ways of selecting $m$ vectors such that they form the rows of a full rank matrix. Observe that the full rank condition is violated if and only if at some point the next vector is a linear combination of the preceding ones. How many choices does that leave for the first vector? How many for the second? At each point it is easier to calculate the number of vectors in violation. Observe that each point you can assume the earlier picks to be linearly independent (because otherwise you are already guaranteed to fail).
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 16:10
1
$begingroup$
Essentially this is a duplicate of this. I won't cast the first vote because A) the case is not 100% clear cut, B) my vote would be binding because of my dupehammer privilege.
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 16:13
1
$begingroup$
An important aspect of the problem setup is left out, namely the size of the finite field from which the vector entries are drawn. That must be a power of a prime, so $q=p^k$ will serve the purpose. Proceed to count the ways to choose the first vector, and continue by induction.
$endgroup$
– hardmath
Dec 12 '18 at 22:17
add a comment |
$begingroup$
Start by considering the choice of the first vector. If it is zero, then the second vector is not independent. So it becomes a counting problem, how many selections of $m$ linearly independent vectors can be formed.
$endgroup$
– hardmath
Dec 12 '18 at 15:43
$begingroup$
@hardmath "how many selections of m linearly independent vectors can be formed". Excuse me, I don't understand this. I'd like to check independency of all m vectors. I need it for getting probability that rank of matrix with these vectors is m.
$endgroup$
– Treasure B
Dec 12 '18 at 16:00
2
$begingroup$
This is just a counting exercise. You are to calculate the number of ways of selecting $m$ vectors such that they form the rows of a full rank matrix. Observe that the full rank condition is violated if and only if at some point the next vector is a linear combination of the preceding ones. How many choices does that leave for the first vector? How many for the second? At each point it is easier to calculate the number of vectors in violation. Observe that each point you can assume the earlier picks to be linearly independent (because otherwise you are already guaranteed to fail).
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 16:10
1
$begingroup$
Essentially this is a duplicate of this. I won't cast the first vote because A) the case is not 100% clear cut, B) my vote would be binding because of my dupehammer privilege.
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 16:13
1
$begingroup$
An important aspect of the problem setup is left out, namely the size of the finite field from which the vector entries are drawn. That must be a power of a prime, so $q=p^k$ will serve the purpose. Proceed to count the ways to choose the first vector, and continue by induction.
$endgroup$
– hardmath
Dec 12 '18 at 22:17
$begingroup$
Start by considering the choice of the first vector. If it is zero, then the second vector is not independent. So it becomes a counting problem, how many selections of $m$ linearly independent vectors can be formed.
$endgroup$
– hardmath
Dec 12 '18 at 15:43
$begingroup$
Start by considering the choice of the first vector. If it is zero, then the second vector is not independent. So it becomes a counting problem, how many selections of $m$ linearly independent vectors can be formed.
$endgroup$
– hardmath
Dec 12 '18 at 15:43
$begingroup$
@hardmath "how many selections of m linearly independent vectors can be formed". Excuse me, I don't understand this. I'd like to check independency of all m vectors. I need it for getting probability that rank of matrix with these vectors is m.
$endgroup$
– Treasure B
Dec 12 '18 at 16:00
$begingroup$
@hardmath "how many selections of m linearly independent vectors can be formed". Excuse me, I don't understand this. I'd like to check independency of all m vectors. I need it for getting probability that rank of matrix with these vectors is m.
$endgroup$
– Treasure B
Dec 12 '18 at 16:00
2
2
$begingroup$
This is just a counting exercise. You are to calculate the number of ways of selecting $m$ vectors such that they form the rows of a full rank matrix. Observe that the full rank condition is violated if and only if at some point the next vector is a linear combination of the preceding ones. How many choices does that leave for the first vector? How many for the second? At each point it is easier to calculate the number of vectors in violation. Observe that each point you can assume the earlier picks to be linearly independent (because otherwise you are already guaranteed to fail).
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 16:10
$begingroup$
This is just a counting exercise. You are to calculate the number of ways of selecting $m$ vectors such that they form the rows of a full rank matrix. Observe that the full rank condition is violated if and only if at some point the next vector is a linear combination of the preceding ones. How many choices does that leave for the first vector? How many for the second? At each point it is easier to calculate the number of vectors in violation. Observe that each point you can assume the earlier picks to be linearly independent (because otherwise you are already guaranteed to fail).
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 16:10
1
1
$begingroup$
Essentially this is a duplicate of this. I won't cast the first vote because A) the case is not 100% clear cut, B) my vote would be binding because of my dupehammer privilege.
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 16:13
$begingroup$
Essentially this is a duplicate of this. I won't cast the first vote because A) the case is not 100% clear cut, B) my vote would be binding because of my dupehammer privilege.
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 16:13
1
1
$begingroup$
An important aspect of the problem setup is left out, namely the size of the finite field from which the vector entries are drawn. That must be a power of a prime, so $q=p^k$ will serve the purpose. Proceed to count the ways to choose the first vector, and continue by induction.
$endgroup$
– hardmath
Dec 12 '18 at 22:17
$begingroup$
An important aspect of the problem setup is left out, namely the size of the finite field from which the vector entries are drawn. That must be a power of a prime, so $q=p^k$ will serve the purpose. Proceed to count the ways to choose the first vector, and continue by induction.
$endgroup$
– hardmath
Dec 12 '18 at 22:17
add a comment |
0
active
oldest
votes
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
});
}
});
draft saved
draft discarded
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%2f3036834%2fprobability-of-linear-independency-of-vectors-under-finite-field%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
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.
draft saved
draft discarded
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%2f3036834%2fprobability-of-linear-independency-of-vectors-under-finite-field%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$
Start by considering the choice of the first vector. If it is zero, then the second vector is not independent. So it becomes a counting problem, how many selections of $m$ linearly independent vectors can be formed.
$endgroup$
– hardmath
Dec 12 '18 at 15:43
$begingroup$
@hardmath "how many selections of m linearly independent vectors can be formed". Excuse me, I don't understand this. I'd like to check independency of all m vectors. I need it for getting probability that rank of matrix with these vectors is m.
$endgroup$
– Treasure B
Dec 12 '18 at 16:00
2
$begingroup$
This is just a counting exercise. You are to calculate the number of ways of selecting $m$ vectors such that they form the rows of a full rank matrix. Observe that the full rank condition is violated if and only if at some point the next vector is a linear combination of the preceding ones. How many choices does that leave for the first vector? How many for the second? At each point it is easier to calculate the number of vectors in violation. Observe that each point you can assume the earlier picks to be linearly independent (because otherwise you are already guaranteed to fail).
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 16:10
1
$begingroup$
Essentially this is a duplicate of this. I won't cast the first vote because A) the case is not 100% clear cut, B) my vote would be binding because of my dupehammer privilege.
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 16:13
1
$begingroup$
An important aspect of the problem setup is left out, namely the size of the finite field from which the vector entries are drawn. That must be a power of a prime, so $q=p^k$ will serve the purpose. Proceed to count the ways to choose the first vector, and continue by induction.
$endgroup$
– hardmath
Dec 12 '18 at 22:17