Show there are $2^n$ forms a $n times n$ matrix can take, preferably via Pascal's triangle
up vote
0
down vote
favorite
Where "a form" for some RRE matrix is its description in terms of the number of all-zero rows it has and the position of pivots in the non-zero rows.
I've tried using induction, the base case is obvious enough:
$$ left[
begin{array}{c}
0
end{array}
right],
left[
begin{array}{c}
1
end{array}
right] rightarrow 2^1$$
After that, I assume that the total number of forms for the $n$ step is $2^n$, which has to be the sum of the different number of forms for each number $0 ,..., n$ of zero rows, the specifics of which I ignore for now (really, because I couldn't prove it myself).
Then, for each $n times n$ form with given number of zero rows $Z$, I can embed it in a $(n+1) times (n+1)$ matrix where the first zero row $z$ from the embedded matrix can be extended to have an $z_{n+1}$ entry in ${1, 0}$. If $z_{n+1} = 0$, there is a one-to-one correspondence with the sets of $ntimes n$ forms indexed by $Z$, except when $Z=0$. The same argument applies to $z_{n+1} = 1$. Notice that for the $Z=0$ case, the smaller matrix can be embedded in a matrix where the last entry is either $0$ or $1$, which results in two RRE additional forms for the larger matrix.
Finally, the two one-to-one mappings contribute $2^n -1$ forms each. Adding the last two cases, we have $2^n - 1 + 2^n -1 +2 = 2^{n+1}$ forms and the induction is complete.
I feel my reasoning is somewhat convoluted, so I'd appreciate it if any flaws could be pointed out. My textbook had a hint about using Pascal's triangle, and I did notice that the number of forms linked to each $Z$ follows the pattern, but I was unable to set up a counting scheme for all possible pivot positions to show that this applies generally, so I would appreciate guidance in that regard.
linear-algebra combinatorics matrices induction binomial-coefficients
asked Nov 28 at 22:21
zipzapboing
979
add a comment |
up vote
0
down vote
favorite
Where "a form" for some RRE matrix is its description in terms of the number of all-zero rows it has and the position of pivots in the non-zero rows.
I've tried using induction, the base case is obvious enough:
$$ left[
begin{array}{c}
0
end{array}
right],
left[
begin{array}{c}
1
end{array}
right] rightarrow 2^1$$
After that, I assume that the total number of forms for the $n$ step is $2^n$, which has to be the sum of the different number of forms for each number $0 ,..., n$ of zero rows, the specifics of which I ignore for now (really, because I couldn't prove it myself).
Then, for each $n times n$ form with given number of zero rows $Z$, I can embed it in a $(n+1) times (n+1)$ matrix where the first zero row $z$ from the embedded matrix can be extended to have an $z_{n+1}$ entry in ${1, 0}$. If $z_{n+1} = 0$, there is a one-to-one correspondence with the sets of $ntimes n$ forms indexed by $Z$, except when $Z=0$. The same argument applies to $z_{n+1} = 1$. Notice that for the $Z=0$ case, the smaller matrix can be embedded in a matrix where the last entry is either $0$ or $1$, which results in two RRE additional forms for the larger matrix.
Finally, the two one-to-one mappings contribute $2^n -1$ forms each. Adding the last two cases, we have $2^n - 1 + 2^n -1 +2 = 2^{n+1}$ forms and the induction is complete.
I feel my reasoning is somewhat convoluted, so I'd appreciate it if any flaws could be pointed out. My textbook had a hint about using Pascal's triangle, and I did notice that the number of forms linked to each $Z$ follows the pattern, but I was unable to set up a counting scheme for all possible pivot positions to show that this applies generally, so I would appreciate guidance in that regard.
linear-algebra combinatorics matrices induction binomial-coefficients
asked Nov 28 at 22:21
zipzapboing
979
What is a n RRE matrix?
– Yiorgos S. Smyrlis
Nov 28 at 22:26
@YiorgosS.Smyrlis I meant to type $n times n$ but the description actually applies to any matrix. RRE means Reduced Row Echelon form.
– zipzapboing
Nov 29 at 0:29
Hint: how many forms are there for an n-by-n matrix with k non-zero rows?
– Michael Lugo
Nov 29 at 1:27
${n choose k}$ and I don't know how to show why
– zipzapboing
Nov 29 at 2:02
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Where "a form" for some RRE matrix is its description in terms of the number of all-zero rows it has and the position of pivots in the non-zero rows.
I've tried using induction, the base case is obvious enough:
$$ left[
begin{array}{c}
0
end{array}
right],
left[
begin{array}{c}
1
end{array}
right] rightarrow 2^1$$
After that, I assume that the total number of forms for the $n$ step is $2^n$, which has to be the sum of the different number of forms for each number $0 ,..., n$ of zero rows, the specifics of which I ignore for now (really, because I couldn't prove it myself).
Then, for each $n times n$ form with given number of zero rows $Z$, I can embed it in a $(n+1) times (n+1)$ matrix where the first zero row $z$ from the embedded matrix can be extended to have an $z_{n+1}$ entry in ${1, 0}$. If $z_{n+1} = 0$, there is a one-to-one correspondence with the sets of $ntimes n$ forms indexed by $Z$, except when $Z=0$. The same argument applies to $z_{n+1} = 1$. Notice that for the $Z=0$ case, the smaller matrix can be embedded in a matrix where the last entry is either $0$ or $1$, which results in two RRE additional forms for the larger matrix.
Finally, the two one-to-one mappings contribute $2^n -1$ forms each. Adding the last two cases, we have $2^n - 1 + 2^n -1 +2 = 2^{n+1}$ forms and the induction is complete.
I feel my reasoning is somewhat convoluted, so I'd appreciate it if any flaws could be pointed out. My textbook had a hint about using Pascal's triangle, and I did notice that the number of forms linked to each $Z$ follows the pattern, but I was unable to set up a counting scheme for all possible pivot positions to show that this applies generally, so I would appreciate guidance in that regard.
linear-algebra combinatorics matrices induction binomial-coefficients
asked Nov 28 at 22:21
zipzapboing
979
Where "a form" for some RRE matrix is its description in terms of the number of all-zero rows it has and the position of pivots in the non-zero rows.
I've tried using induction, the base case is obvious enough:
$$ left[
begin{array}{c}
0
end{array}
right],
left[
begin{array}{c}
1
end{array}
right] rightarrow 2^1$$
After that, I assume that the total number of forms for the $n$ step is $2^n$, which has to be the sum of the different number of forms for each number $0 ,..., n$ of zero rows, the specifics of which I ignore for now (really, because I couldn't prove it myself).
Then, for each $n times n$ form with given number of zero rows $Z$, I can embed it in a $(n+1) times (n+1)$ matrix where the first zero row $z$ from the embedded matrix can be extended to have an $z_{n+1}$ entry in ${1, 0}$. If $z_{n+1} = 0$, there is a one-to-one correspondence with the sets of $ntimes n$ forms indexed by $Z$, except when $Z=0$. The same argument applies to $z_{n+1} = 1$. Notice that for the $Z=0$ case, the smaller matrix can be embedded in a matrix where the last entry is either $0$ or $1$, which results in two RRE additional forms for the larger matrix.
Finally, the two one-to-one mappings contribute $2^n -1$ forms each. Adding the last two cases, we have $2^n - 1 + 2^n -1 +2 = 2^{n+1}$ forms and the induction is complete.
I feel my reasoning is somewhat convoluted, so I'd appreciate it if any flaws could be pointed out. My textbook had a hint about using Pascal's triangle, and I did notice that the number of forms linked to each $Z$ follows the pattern, but I was unable to set up a counting scheme for all possible pivot positions to show that this applies generally, so I would appreciate guidance in that regard.
linear-algebra combinatorics matrices induction binomial-coefficients
linear-algebra combinatorics matrices induction binomial-coefficients
asked Nov 28 at 22:21
zipzapboing
979
asked Nov 28 at 22:21
zipzapboing
979
edited Nov 29 at 0:28
asked Nov 28 at 22:21
zipzapboing
979
asked Nov 28 at 22:21
zipzapboing
979
asked Nov 28 at 22:21
zipzapboing
979
979
What is a n RRE matrix?
– Yiorgos S. Smyrlis
Nov 28 at 22:26
@YiorgosS.Smyrlis I meant to type $n times n$ but the description actually applies to any matrix. RRE means Reduced Row Echelon form.
– zipzapboing
Nov 29 at 0:29
Hint: how many forms are there for an n-by-n matrix with k non-zero rows?
– Michael Lugo
Nov 29 at 1:27
${n choose k}$ and I don't know how to show why
– zipzapboing
Nov 29 at 2:02
add a comment |
What is a n RRE matrix?
– Yiorgos S. Smyrlis
Nov 28 at 22:26
@YiorgosS.Smyrlis I meant to type $n times n$ but the description actually applies to any matrix. RRE means Reduced Row Echelon form.
– zipzapboing
Nov 29 at 0:29
Hint: how many forms are there for an n-by-n matrix with k non-zero rows?
– Michael Lugo
Nov 29 at 1:27
${n choose k}$ and I don't know how to show why
– zipzapboing
Nov 29 at 2:02
What is a n RRE matrix?
– Yiorgos S. Smyrlis
Nov 28 at 22:26
What is a n RRE matrix?
– Yiorgos S. Smyrlis
Nov 28 at 22:26
@YiorgosS.Smyrlis I meant to type $n times n$ but the description actually applies to any matrix. RRE means Reduced Row Echelon form.
– zipzapboing
Nov 29 at 0:29
@YiorgosS.Smyrlis I meant to type $n times n$ but the description actually applies to any matrix. RRE means Reduced Row Echelon form.
– zipzapboing
Nov 29 at 0:29
Hint: how many forms are there for an n-by-n matrix with k non-zero rows?
– Michael Lugo
Nov 29 at 1:27
Hint: how many forms are there for an n-by-n matrix with k non-zero rows?
– Michael Lugo
Nov 29 at 1:27
${n choose k}$ and I don't know how to show why
– zipzapboing
Nov 29 at 2:02
${n choose k}$ and I don't know how to show why
– zipzapboing
Nov 29 at 2:02
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
A form with $k$ non-zero rows will have $k$ pivots which can be in columns $1,...,n$. Since the pivots must be ordered so that each one is to the right of the previous one, they can only be picked in increasing order, that is, only one ordering matters and this is equivalent to picking a combination of $k$ in $n$ elements.
Therefore, for a given $n times n$ matrix, we have $sum_{k=0}^n {n choose k} = 2^n$ forms.
answered Nov 30 at 1:57
zipzapboing
979
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%2f3017819%2fshow-there-are-2n-forms-a-n-times-n-matrix-can-take-preferably-via-pascal%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
A form with $k$ non-zero rows will have $k$ pivots which can be in columns $1,...,n$. Since the pivots must be ordered so that each one is to the right of the previous one, they can only be picked in increasing order, that is, only one ordering matters and this is equivalent to picking a combination of $k$ in $n$ elements.
Therefore, for a given $n times n$ matrix, we have $sum_{k=0}^n {n choose k} = 2^n$ forms.
answered Nov 30 at 1:57
zipzapboing
979
add a comment |
up vote
0
down vote
accepted
A form with $k$ non-zero rows will have $k$ pivots which can be in columns $1,...,n$. Since the pivots must be ordered so that each one is to the right of the previous one, they can only be picked in increasing order, that is, only one ordering matters and this is equivalent to picking a combination of $k$ in $n$ elements.
Therefore, for a given $n times n$ matrix, we have $sum_{k=0}^n {n choose k} = 2^n$ forms.
answered Nov 30 at 1:57
zipzapboing
979
add a comment |
up vote
0
down vote
accepted
up vote
0
down vote
accepted
A form with $k$ non-zero rows will have $k$ pivots which can be in columns $1,...,n$. Since the pivots must be ordered so that each one is to the right of the previous one, they can only be picked in increasing order, that is, only one ordering matters and this is equivalent to picking a combination of $k$ in $n$ elements.
Therefore, for a given $n times n$ matrix, we have $sum_{k=0}^n {n choose k} = 2^n$ forms.
answered Nov 30 at 1:57
zipzapboing
979
A form with $k$ non-zero rows will have $k$ pivots which can be in columns $1,...,n$. Since the pivots must be ordered so that each one is to the right of the previous one, they can only be picked in increasing order, that is, only one ordering matters and this is equivalent to picking a combination of $k$ in $n$ elements.
Therefore, for a given $n times n$ matrix, we have $sum_{k=0}^n {n choose k} = 2^n$ forms.
answered Nov 30 at 1:57
zipzapboing
979
answered Nov 30 at 1:57
zipzapboing
979
answered Nov 30 at 1:57
zipzapboing
979
answered Nov 30 at 1:57
zipzapboing
979
979
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3017819%2fshow-there-are-2n-forms-a-n-times-n-matrix-can-take-preferably-via-pascal%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
What is a n RRE matrix?
– Yiorgos S. Smyrlis
Nov 28 at 22:26
@YiorgosS.Smyrlis I meant to type $n times n$ but the description actually applies to any matrix. RRE means Reduced Row Echelon form.
– zipzapboing
Nov 29 at 0:29
Hint: how many forms are there for an n-by-n matrix with k non-zero rows?
– Michael Lugo
Nov 29 at 1:27
${n choose k}$ and I don't know how to show why
– zipzapboing
Nov 29 at 2:02