The number of non-singular $ntimes n$ matrices over $mathbb{F}_2$ with exactly $k$ non-zero entries
Suppose $M_{n}^{k}$ is the number of non-singular $ntimes n$ matrices over $mathbb{F}_2$, that have exactly $k$ non-zero entries.
Is there some sort of formula to calculate $M_n^k$?
If $k < n$ or $k > n^2 - n + 1$, then $M_n^k = 0$ by pigeonhole principle (in the first case we always have at least one zero row, in the second case we always have at least two identical rows).
If $k = n$, then all such non-singular matrices have to be permutation matrices. Thus $M_n^n = n!$.
However, I do not know, how to deal with the situation, where $n < k < n^2 - n + 1$.
Any help will be appreciated.
linear-algebra abstract-algebra combinatorics matrices finite-fields
asked Dec 8 '18 at 8:24
Yanior WegYanior Weg
1,1151935
This question has an open bounty worth +100
reputation from Yanior Weg ending in 5 days.
This question has not received enough attention.
|
show 1 more comment
Suppose $M_{n}^{k}$ is the number of non-singular $ntimes n$ matrices over $mathbb{F}_2$, that have exactly $k$ non-zero entries.
Is there some sort of formula to calculate $M_n^k$?
If $k < n$ or $k > n^2 - n + 1$, then $M_n^k = 0$ by pigeonhole principle (in the first case we always have at least one zero row, in the second case we always have at least two identical rows).
If $k = n$, then all such non-singular matrices have to be permutation matrices. Thus $M_n^n = n!$.
However, I do not know, how to deal with the situation, where $n < k < n^2 - n + 1$.
Any help will be appreciated.
linear-algebra abstract-algebra combinatorics matrices finite-fields
asked Dec 8 '18 at 8:24
Yanior WegYanior Weg
1,1151935
This question has an open bounty worth +100
reputation from Yanior Weg ending in 5 days.
This question has not received enough attention.
3
One more easy case: if $k=n+1$ then you must have a permutation matrix plus one more $1$ (which can be anywhere). The permutation matrix is uniquely determined (all but one of the columns have only one $1$ and a permutation is determined by its values on all but one point) so that gives $n!(n^2-n)$ possibilities.
– Eric Wofsey
Dec 8 '18 at 8:49
If $k=n+2$, there are $$n!(n^2-n)(n^2-n-2)/2$$ possibilities.
– san
Dec 12 '18 at 18:25
1
Another case: if $k = n^2 - n + 1$, there are $n-1$ zeros and they must necessarily be on different columns and different rows (otherwise there are 2 columns or 2 rows with all $1$s). So the $n-1$ zeros also define a permutation (of which one entry gets replaced by a $1$). Thus $M le n! times n$. For sufficiency: consider any subset of $c>1$ columns. Since $c > 1$, at least $1$ row has exactly one $0$ in it. Also, there exists a row with all $1$s in it. These $2$ rows cannot simultaneously sum to $0$. So any subset is independent and the matrix is non-singular. So $M = n! n$.
– antkam
Dec 12 '18 at 20:29
3
If $k=n+2$, you can start with a permutation matrix $P$, i.e., $P_{i,j}=delta_{j,sigma(i)}$, where $sigma$ is a permutation. Then you have to add two non-zero entries. So you have $binom {n^2-n}{2}$ choices. But if one entry is $i,j$, you cannot choose the entry $sigma^{-1}(j),sigma(i)$ as the other entry, and this is the only exception, so you have $frac{n^2-n}{2}$ invalid pairs. Then you have $$ binom {n^2-n}{2}-frac{n^2-n}{2}=(n^2−n)(n^2−n−2)/2 $$ valid pairs, and so the total number of non-singular matrices is $$ n!(n^2−n)(n^2−n−2)/2. $$
– san
Dec 14 '18 at 6:38
2
It gets ugly very rapidly. If $k=n+3$ and you start from a permutation, you have to rule out adding the trhree additional 1's at $(i,j),(k,sigma(i)),(sigma^{-1}(j),sigma(k))$, besides the previous restrictions.
– san
Dec 14 '18 at 7:09
|
show 1 more comment
Suppose $M_{n}^{k}$ is the number of non-singular $ntimes n$ matrices over $mathbb{F}_2$, that have exactly $k$ non-zero entries.
Is there some sort of formula to calculate $M_n^k$?
If $k < n$ or $k > n^2 - n + 1$, then $M_n^k = 0$ by pigeonhole principle (in the first case we always have at least one zero row, in the second case we always have at least two identical rows).
If $k = n$, then all such non-singular matrices have to be permutation matrices. Thus $M_n^n = n!$.
However, I do not know, how to deal with the situation, where $n < k < n^2 - n + 1$.
Any help will be appreciated.
linear-algebra abstract-algebra combinatorics matrices finite-fields
asked Dec 8 '18 at 8:24
Yanior WegYanior Weg
1,1151935
Suppose $M_{n}^{k}$ is the number of non-singular $ntimes n$ matrices over $mathbb{F}_2$, that have exactly $k$ non-zero entries.
Is there some sort of formula to calculate $M_n^k$?
If $k < n$ or $k > n^2 - n + 1$, then $M_n^k = 0$ by pigeonhole principle (in the first case we always have at least one zero row, in the second case we always have at least two identical rows).
If $k = n$, then all such non-singular matrices have to be permutation matrices. Thus $M_n^n = n!$.
However, I do not know, how to deal with the situation, where $n < k < n^2 - n + 1$.
Any help will be appreciated.
linear-algebra abstract-algebra combinatorics matrices finite-fields
linear-algebra abstract-algebra combinatorics matrices finite-fields
asked Dec 8 '18 at 8:24
Yanior WegYanior Weg
1,1151935
asked Dec 8 '18 at 8:24
Yanior WegYanior Weg
1,1151935
edited Dec 8 '18 at 8:32
Yanior Weg
asked Dec 8 '18 at 8:24
Yanior WegYanior Weg
1,1151935
asked Dec 8 '18 at 8:24
Yanior WegYanior Weg
1,1151935
asked Dec 8 '18 at 8:24
Yanior WegYanior Weg
1,1151935
1,1151935
This question has an open bounty worth +100
reputation from Yanior Weg ending in 5 days.
This question has not received enough attention.
This question has an open bounty worth +100
reputation from Yanior Weg ending in 5 days.
This question has not received enough attention.
3
One more easy case: if $k=n+1$ then you must have a permutation matrix plus one more $1$ (which can be anywhere). The permutation matrix is uniquely determined (all but one of the columns have only one $1$ and a permutation is determined by its values on all but one point) so that gives $n!(n^2-n)$ possibilities.
– Eric Wofsey
Dec 8 '18 at 8:49
If $k=n+2$, there are $$n!(n^2-n)(n^2-n-2)/2$$ possibilities.
– san
Dec 12 '18 at 18:25
1
Another case: if $k = n^2 - n + 1$, there are $n-1$ zeros and they must necessarily be on different columns and different rows (otherwise there are 2 columns or 2 rows with all $1$s). So the $n-1$ zeros also define a permutation (of which one entry gets replaced by a $1$). Thus $M le n! times n$. For sufficiency: consider any subset of $c>1$ columns. Since $c > 1$, at least $1$ row has exactly one $0$ in it. Also, there exists a row with all $1$s in it. These $2$ rows cannot simultaneously sum to $0$. So any subset is independent and the matrix is non-singular. So $M = n! n$.
– antkam
Dec 12 '18 at 20:29
3
If $k=n+2$, you can start with a permutation matrix $P$, i.e., $P_{i,j}=delta_{j,sigma(i)}$, where $sigma$ is a permutation. Then you have to add two non-zero entries. So you have $binom {n^2-n}{2}$ choices. But if one entry is $i,j$, you cannot choose the entry $sigma^{-1}(j),sigma(i)$ as the other entry, and this is the only exception, so you have $frac{n^2-n}{2}$ invalid pairs. Then you have $$ binom {n^2-n}{2}-frac{n^2-n}{2}=(n^2−n)(n^2−n−2)/2 $$ valid pairs, and so the total number of non-singular matrices is $$ n!(n^2−n)(n^2−n−2)/2. $$
– san
Dec 14 '18 at 6:38
2
It gets ugly very rapidly. If $k=n+3$ and you start from a permutation, you have to rule out adding the trhree additional 1's at $(i,j),(k,sigma(i)),(sigma^{-1}(j),sigma(k))$, besides the previous restrictions.
– san
Dec 14 '18 at 7:09
|
show 1 more comment
3
One more easy case: if $k=n+1$ then you must have a permutation matrix plus one more $1$ (which can be anywhere). The permutation matrix is uniquely determined (all but one of the columns have only one $1$ and a permutation is determined by its values on all but one point) so that gives $n!(n^2-n)$ possibilities.
– Eric Wofsey
Dec 8 '18 at 8:49
If $k=n+2$, there are $$n!(n^2-n)(n^2-n-2)/2$$ possibilities.
– san
Dec 12 '18 at 18:25
1
Another case: if $k = n^2 - n + 1$, there are $n-1$ zeros and they must necessarily be on different columns and different rows (otherwise there are 2 columns or 2 rows with all $1$s). So the $n-1$ zeros also define a permutation (of which one entry gets replaced by a $1$). Thus $M le n! times n$. For sufficiency: consider any subset of $c>1$ columns. Since $c > 1$, at least $1$ row has exactly one $0$ in it. Also, there exists a row with all $1$s in it. These $2$ rows cannot simultaneously sum to $0$. So any subset is independent and the matrix is non-singular. So $M = n! n$.
– antkam
Dec 12 '18 at 20:29
3
If $k=n+2$, you can start with a permutation matrix $P$, i.e., $P_{i,j}=delta_{j,sigma(i)}$, where $sigma$ is a permutation. Then you have to add two non-zero entries. So you have $binom {n^2-n}{2}$ choices. But if one entry is $i,j$, you cannot choose the entry $sigma^{-1}(j),sigma(i)$ as the other entry, and this is the only exception, so you have $frac{n^2-n}{2}$ invalid pairs. Then you have $$ binom {n^2-n}{2}-frac{n^2-n}{2}=(n^2−n)(n^2−n−2)/2 $$ valid pairs, and so the total number of non-singular matrices is $$ n!(n^2−n)(n^2−n−2)/2. $$
– san
Dec 14 '18 at 6:38
2
It gets ugly very rapidly. If $k=n+3$ and you start from a permutation, you have to rule out adding the trhree additional 1's at $(i,j),(k,sigma(i)),(sigma^{-1}(j),sigma(k))$, besides the previous restrictions.
– san
Dec 14 '18 at 7:09
3
3
One more easy case: if $k=n+1$ then you must have a permutation matrix plus one more $1$ (which can be anywhere). The permutation matrix is uniquely determined (all but one of the columns have only one $1$ and a permutation is determined by its values on all but one point) so that gives $n!(n^2-n)$ possibilities.
– Eric Wofsey
Dec 8 '18 at 8:49
One more easy case: if $k=n+1$ then you must have a permutation matrix plus one more $1$ (which can be anywhere). The permutation matrix is uniquely determined (all but one of the columns have only one $1$ and a permutation is determined by its values on all but one point) so that gives $n!(n^2-n)$ possibilities.
– Eric Wofsey
Dec 8 '18 at 8:49
If $k=n+2$, there are $$n!(n^2-n)(n^2-n-2)/2$$ possibilities.
– san
Dec 12 '18 at 18:25
If $k=n+2$, there are $$n!(n^2-n)(n^2-n-2)/2$$ possibilities.
– san
Dec 12 '18 at 18:25
1
1
Another case: if $k = n^2 - n + 1$, there are $n-1$ zeros and they must necessarily be on different columns and different rows (otherwise there are 2 columns or 2 rows with all $1$s). So the $n-1$ zeros also define a permutation (of which one entry gets replaced by a $1$). Thus $M le n! times n$. For sufficiency: consider any subset of $c>1$ columns. Since $c > 1$, at least $1$ row has exactly one $0$ in it. Also, there exists a row with all $1$s in it. These $2$ rows cannot simultaneously sum to $0$. So any subset is independent and the matrix is non-singular. So $M = n! n$.
– antkam
Dec 12 '18 at 20:29
Another case: if $k = n^2 - n + 1$, there are $n-1$ zeros and they must necessarily be on different columns and different rows (otherwise there are 2 columns or 2 rows with all $1$s). So the $n-1$ zeros also define a permutation (of which one entry gets replaced by a $1$). Thus $M le n! times n$. For sufficiency: consider any subset of $c>1$ columns. Since $c > 1$, at least $1$ row has exactly one $0$ in it. Also, there exists a row with all $1$s in it. These $2$ rows cannot simultaneously sum to $0$. So any subset is independent and the matrix is non-singular. So $M = n! n$.
– antkam
Dec 12 '18 at 20:29
3
3
If $k=n+2$, you can start with a permutation matrix $P$, i.e., $P_{i,j}=delta_{j,sigma(i)}$, where $sigma$ is a permutation. Then you have to add two non-zero entries. So you have $binom {n^2-n}{2}$ choices. But if one entry is $i,j$, you cannot choose the entry $sigma^{-1}(j),sigma(i)$ as the other entry, and this is the only exception, so you have $frac{n^2-n}{2}$ invalid pairs. Then you have $$ binom {n^2-n}{2}-frac{n^2-n}{2}=(n^2−n)(n^2−n−2)/2 $$ valid pairs, and so the total number of non-singular matrices is $$ n!(n^2−n)(n^2−n−2)/2. $$
– san
Dec 14 '18 at 6:38
If $k=n+2$, you can start with a permutation matrix $P$, i.e., $P_{i,j}=delta_{j,sigma(i)}$, where $sigma$ is a permutation. Then you have to add two non-zero entries. So you have $binom {n^2-n}{2}$ choices. But if one entry is $i,j$, you cannot choose the entry $sigma^{-1}(j),sigma(i)$ as the other entry, and this is the only exception, so you have $frac{n^2-n}{2}$ invalid pairs. Then you have $$ binom {n^2-n}{2}-frac{n^2-n}{2}=(n^2−n)(n^2−n−2)/2 $$ valid pairs, and so the total number of non-singular matrices is $$ n!(n^2−n)(n^2−n−2)/2. $$
– san
Dec 14 '18 at 6:38
2
2
It gets ugly very rapidly. If $k=n+3$ and you start from a permutation, you have to rule out adding the trhree additional 1's at $(i,j),(k,sigma(i)),(sigma^{-1}(j),sigma(k))$, besides the previous restrictions.
– san
Dec 14 '18 at 7:09
It gets ugly very rapidly. If $k=n+3$ and you start from a permutation, you have to rule out adding the trhree additional 1's at $(i,j),(k,sigma(i)),(sigma^{-1}(j),sigma(k))$, besides the previous restrictions.
– san
Dec 14 '18 at 7:09
|
show 1 more comment
1 Answer
1
active
oldest
votes
I think there is a way to generate the matrices :
We start with a permutation matrix $P$. There are $n!$ permutations with each of them having $n$ non zero entries.
So now we are going to add $ E_1 $ such that $E_1$ equals zero everywhere except its $(i,j)$ entry. We want the sum to still be non-singular so $i$ and $j$ can take $n^2-n$ values in total. We can add a one to any entry that was previously zero.
If we want to add another matrix $E_2$ we have $n^2 - n -1$ possible entries for the non zero element. If we repeat the process $m$ times $Card(E_m)=n^2-(n+m-1)$. We continue until $m$ verifies that $m=k-n .$ And we have generated a non singular matrix with exactly $k$ non zero entries.
We can conclude that: $$M_k^n=(n!*(n^2-n)*(n^2-n-1)...*(n^2-k+1)).$$
We just multiplied the number of possibilites allowed at each step of the process. I'am not 100% sure so if anything seems out of touch please tell me.
All this reasoning for $n<k<n^2 -n +1 $.
answered Dec 13 '18 at 23:17
NassoumoNassoumo
362
How do you reason that $i$ and $j$ can take $n^2-n$ values for the matrix to remain non-singular?
– Will Fisher
Dec 14 '18 at 0:10
There aren't $n^2 - n - 1$ possibilities for $E_2$. Without loss you can imagine the original permutation to be the identity matrix, and the $E_1$ to have its $1$ at $(0,1)$. Then you cannot add another $1$ at $(1,0)$. I think this is the only prohibited spot, so $E_2$ has $n^2 - n - 2$ possibilities for the matrix to remain singular. But I don't think this kind of logic generalizes easily beyond $E_2$...
– antkam
Dec 14 '18 at 1:04
The reasoning to justify that $i$ and $j$ can take $n^2-n$ values is that the permutation matrix contains $n$ non zero entries. And $i$ and $ j$ can initialy take any $n^2$ value if we do not add any constraint but we don't want to add a 1 to another 1 because if would become a 0 in the sum of the matrices. So how many possibilities remain ? Well the initial number of positions minus the number of positions already filled with a non zero entry. Did you find this helpful ?
– Nassoumo
Dec 14 '18 at 11:08
do you understand what "non-singular" mean?
– antkam
Dec 15 '18 at 3:57
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%2f3030828%2fthe-number-of-non-singular-n-times-n-matrices-over-mathbbf-2-with-exactly%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
I think there is a way to generate the matrices :
We start with a permutation matrix $P$. There are $n!$ permutations with each of them having $n$ non zero entries.
So now we are going to add $ E_1 $ such that $E_1$ equals zero everywhere except its $(i,j)$ entry. We want the sum to still be non-singular so $i$ and $j$ can take $n^2-n$ values in total. We can add a one to any entry that was previously zero.
If we want to add another matrix $E_2$ we have $n^2 - n -1$ possible entries for the non zero element. If we repeat the process $m$ times $Card(E_m)=n^2-(n+m-1)$. We continue until $m$ verifies that $m=k-n .$ And we have generated a non singular matrix with exactly $k$ non zero entries.
We can conclude that: $$M_k^n=(n!*(n^2-n)*(n^2-n-1)...*(n^2-k+1)).$$
We just multiplied the number of possibilites allowed at each step of the process. I'am not 100% sure so if anything seems out of touch please tell me.
All this reasoning for $n<k<n^2 -n +1 $.
answered Dec 13 '18 at 23:17
NassoumoNassoumo
362
How do you reason that $i$ and $j$ can take $n^2-n$ values for the matrix to remain non-singular?
– Will Fisher
Dec 14 '18 at 0:10
There aren't $n^2 - n - 1$ possibilities for $E_2$. Without loss you can imagine the original permutation to be the identity matrix, and the $E_1$ to have its $1$ at $(0,1)$. Then you cannot add another $1$ at $(1,0)$. I think this is the only prohibited spot, so $E_2$ has $n^2 - n - 2$ possibilities for the matrix to remain singular. But I don't think this kind of logic generalizes easily beyond $E_2$...
– antkam
Dec 14 '18 at 1:04
The reasoning to justify that $i$ and $j$ can take $n^2-n$ values is that the permutation matrix contains $n$ non zero entries. And $i$ and $ j$ can initialy take any $n^2$ value if we do not add any constraint but we don't want to add a 1 to another 1 because if would become a 0 in the sum of the matrices. So how many possibilities remain ? Well the initial number of positions minus the number of positions already filled with a non zero entry. Did you find this helpful ?
– Nassoumo
Dec 14 '18 at 11:08
do you understand what "non-singular" mean?
– antkam
Dec 15 '18 at 3:57
add a comment |
I think there is a way to generate the matrices :
We start with a permutation matrix $P$. There are $n!$ permutations with each of them having $n$ non zero entries.
So now we are going to add $ E_1 $ such that $E_1$ equals zero everywhere except its $(i,j)$ entry. We want the sum to still be non-singular so $i$ and $j$ can take $n^2-n$ values in total. We can add a one to any entry that was previously zero.
If we want to add another matrix $E_2$ we have $n^2 - n -1$ possible entries for the non zero element. If we repeat the process $m$ times $Card(E_m)=n^2-(n+m-1)$. We continue until $m$ verifies that $m=k-n .$ And we have generated a non singular matrix with exactly $k$ non zero entries.
We can conclude that: $$M_k^n=(n!*(n^2-n)*(n^2-n-1)...*(n^2-k+1)).$$
We just multiplied the number of possibilites allowed at each step of the process. I'am not 100% sure so if anything seems out of touch please tell me.
All this reasoning for $n<k<n^2 -n +1 $.
answered Dec 13 '18 at 23:17
NassoumoNassoumo
362
How do you reason that $i$ and $j$ can take $n^2-n$ values for the matrix to remain non-singular?
– Will Fisher
Dec 14 '18 at 0:10
There aren't $n^2 - n - 1$ possibilities for $E_2$. Without loss you can imagine the original permutation to be the identity matrix, and the $E_1$ to have its $1$ at $(0,1)$. Then you cannot add another $1$ at $(1,0)$. I think this is the only prohibited spot, so $E_2$ has $n^2 - n - 2$ possibilities for the matrix to remain singular. But I don't think this kind of logic generalizes easily beyond $E_2$...
– antkam
Dec 14 '18 at 1:04
The reasoning to justify that $i$ and $j$ can take $n^2-n$ values is that the permutation matrix contains $n$ non zero entries. And $i$ and $ j$ can initialy take any $n^2$ value if we do not add any constraint but we don't want to add a 1 to another 1 because if would become a 0 in the sum of the matrices. So how many possibilities remain ? Well the initial number of positions minus the number of positions already filled with a non zero entry. Did you find this helpful ?
– Nassoumo
Dec 14 '18 at 11:08
do you understand what "non-singular" mean?
– antkam
Dec 15 '18 at 3:57
add a comment |
I think there is a way to generate the matrices :
We start with a permutation matrix $P$. There are $n!$ permutations with each of them having $n$ non zero entries.
So now we are going to add $ E_1 $ such that $E_1$ equals zero everywhere except its $(i,j)$ entry. We want the sum to still be non-singular so $i$ and $j$ can take $n^2-n$ values in total. We can add a one to any entry that was previously zero.
If we want to add another matrix $E_2$ we have $n^2 - n -1$ possible entries for the non zero element. If we repeat the process $m$ times $Card(E_m)=n^2-(n+m-1)$. We continue until $m$ verifies that $m=k-n .$ And we have generated a non singular matrix with exactly $k$ non zero entries.
We can conclude that: $$M_k^n=(n!*(n^2-n)*(n^2-n-1)...*(n^2-k+1)).$$
We just multiplied the number of possibilites allowed at each step of the process. I'am not 100% sure so if anything seems out of touch please tell me.
All this reasoning for $n<k<n^2 -n +1 $.
answered Dec 13 '18 at 23:17
NassoumoNassoumo
362
I think there is a way to generate the matrices :
We start with a permutation matrix $P$. There are $n!$ permutations with each of them having $n$ non zero entries.
So now we are going to add $ E_1 $ such that $E_1$ equals zero everywhere except its $(i,j)$ entry. We want the sum to still be non-singular so $i$ and $j$ can take $n^2-n$ values in total. We can add a one to any entry that was previously zero.
If we want to add another matrix $E_2$ we have $n^2 - n -1$ possible entries for the non zero element. If we repeat the process $m$ times $Card(E_m)=n^2-(n+m-1)$. We continue until $m$ verifies that $m=k-n .$ And we have generated a non singular matrix with exactly $k$ non zero entries.
We can conclude that: $$M_k^n=(n!*(n^2-n)*(n^2-n-1)...*(n^2-k+1)).$$
We just multiplied the number of possibilites allowed at each step of the process. I'am not 100% sure so if anything seems out of touch please tell me.
All this reasoning for $n<k<n^2 -n +1 $.
answered Dec 13 '18 at 23:17
NassoumoNassoumo
362
answered Dec 13 '18 at 23:17
NassoumoNassoumo
362
answered Dec 13 '18 at 23:17
NassoumoNassoumo
362
answered Dec 13 '18 at 23:17
NassoumoNassoumo
362
362
How do you reason that $i$ and $j$ can take $n^2-n$ values for the matrix to remain non-singular?
– Will Fisher
Dec 14 '18 at 0:10
There aren't $n^2 - n - 1$ possibilities for $E_2$. Without loss you can imagine the original permutation to be the identity matrix, and the $E_1$ to have its $1$ at $(0,1)$. Then you cannot add another $1$ at $(1,0)$. I think this is the only prohibited spot, so $E_2$ has $n^2 - n - 2$ possibilities for the matrix to remain singular. But I don't think this kind of logic generalizes easily beyond $E_2$...
– antkam
Dec 14 '18 at 1:04
The reasoning to justify that $i$ and $j$ can take $n^2-n$ values is that the permutation matrix contains $n$ non zero entries. And $i$ and $ j$ can initialy take any $n^2$ value if we do not add any constraint but we don't want to add a 1 to another 1 because if would become a 0 in the sum of the matrices. So how many possibilities remain ? Well the initial number of positions minus the number of positions already filled with a non zero entry. Did you find this helpful ?
– Nassoumo
Dec 14 '18 at 11:08
do you understand what "non-singular" mean?
– antkam
Dec 15 '18 at 3:57
add a comment |
How do you reason that $i$ and $j$ can take $n^2-n$ values for the matrix to remain non-singular?
– Will Fisher
Dec 14 '18 at 0:10
There aren't $n^2 - n - 1$ possibilities for $E_2$. Without loss you can imagine the original permutation to be the identity matrix, and the $E_1$ to have its $1$ at $(0,1)$. Then you cannot add another $1$ at $(1,0)$. I think this is the only prohibited spot, so $E_2$ has $n^2 - n - 2$ possibilities for the matrix to remain singular. But I don't think this kind of logic generalizes easily beyond $E_2$...
– antkam
Dec 14 '18 at 1:04
The reasoning to justify that $i$ and $j$ can take $n^2-n$ values is that the permutation matrix contains $n$ non zero entries. And $i$ and $ j$ can initialy take any $n^2$ value if we do not add any constraint but we don't want to add a 1 to another 1 because if would become a 0 in the sum of the matrices. So how many possibilities remain ? Well the initial number of positions minus the number of positions already filled with a non zero entry. Did you find this helpful ?
– Nassoumo
Dec 14 '18 at 11:08
do you understand what "non-singular" mean?
– antkam
Dec 15 '18 at 3:57
How do you reason that $i$ and $j$ can take $n^2-n$ values for the matrix to remain non-singular?
– Will Fisher
Dec 14 '18 at 0:10
How do you reason that $i$ and $j$ can take $n^2-n$ values for the matrix to remain non-singular?
– Will Fisher
Dec 14 '18 at 0:10
There aren't $n^2 - n - 1$ possibilities for $E_2$. Without loss you can imagine the original permutation to be the identity matrix, and the $E_1$ to have its $1$ at $(0,1)$. Then you cannot add another $1$ at $(1,0)$. I think this is the only prohibited spot, so $E_2$ has $n^2 - n - 2$ possibilities for the matrix to remain singular. But I don't think this kind of logic generalizes easily beyond $E_2$...
– antkam
Dec 14 '18 at 1:04
There aren't $n^2 - n - 1$ possibilities for $E_2$. Without loss you can imagine the original permutation to be the identity matrix, and the $E_1$ to have its $1$ at $(0,1)$. Then you cannot add another $1$ at $(1,0)$. I think this is the only prohibited spot, so $E_2$ has $n^2 - n - 2$ possibilities for the matrix to remain singular. But I don't think this kind of logic generalizes easily beyond $E_2$...
– antkam
Dec 14 '18 at 1:04
The reasoning to justify that $i$ and $j$ can take $n^2-n$ values is that the permutation matrix contains $n$ non zero entries. And $i$ and $ j$ can initialy take any $n^2$ value if we do not add any constraint but we don't want to add a 1 to another 1 because if would become a 0 in the sum of the matrices. So how many possibilities remain ? Well the initial number of positions minus the number of positions already filled with a non zero entry. Did you find this helpful ?
– Nassoumo
Dec 14 '18 at 11:08
The reasoning to justify that $i$ and $j$ can take $n^2-n$ values is that the permutation matrix contains $n$ non zero entries. And $i$ and $ j$ can initialy take any $n^2$ value if we do not add any constraint but we don't want to add a 1 to another 1 because if would become a 0 in the sum of the matrices. So how many possibilities remain ? Well the initial number of positions minus the number of positions already filled with a non zero entry. Did you find this helpful ?
– Nassoumo
Dec 14 '18 at 11:08
do you understand what "non-singular" mean?
– antkam
Dec 15 '18 at 3:57
do you understand what "non-singular" mean?
– antkam
Dec 15 '18 at 3:57
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%2f3030828%2fthe-number-of-non-singular-n-times-n-matrices-over-mathbbf-2-with-exactly%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
3
One more easy case: if $k=n+1$ then you must have a permutation matrix plus one more $1$ (which can be anywhere). The permutation matrix is uniquely determined (all but one of the columns have only one $1$ and a permutation is determined by its values on all but one point) so that gives $n!(n^2-n)$ possibilities.
– Eric Wofsey
Dec 8 '18 at 8:49
If $k=n+2$, there are $$n!(n^2-n)(n^2-n-2)/2$$ possibilities.
– san
Dec 12 '18 at 18:25
1
Another case: if $k = n^2 - n + 1$, there are $n-1$ zeros and they must necessarily be on different columns and different rows (otherwise there are 2 columns or 2 rows with all $1$s). So the $n-1$ zeros also define a permutation (of which one entry gets replaced by a $1$). Thus $M le n! times n$. For sufficiency: consider any subset of $c>1$ columns. Since $c > 1$, at least $1$ row has exactly one $0$ in it. Also, there exists a row with all $1$s in it. These $2$ rows cannot simultaneously sum to $0$. So any subset is independent and the matrix is non-singular. So $M = n! n$.
– antkam
Dec 12 '18 at 20:29
3
If $k=n+2$, you can start with a permutation matrix $P$, i.e., $P_{i,j}=delta_{j,sigma(i)}$, where $sigma$ is a permutation. Then you have to add two non-zero entries. So you have $binom {n^2-n}{2}$ choices. But if one entry is $i,j$, you cannot choose the entry $sigma^{-1}(j),sigma(i)$ as the other entry, and this is the only exception, so you have $frac{n^2-n}{2}$ invalid pairs. Then you have $$ binom {n^2-n}{2}-frac{n^2-n}{2}=(n^2−n)(n^2−n−2)/2 $$ valid pairs, and so the total number of non-singular matrices is $$ n!(n^2−n)(n^2−n−2)/2. $$
– san
Dec 14 '18 at 6:38
2
It gets ugly very rapidly. If $k=n+3$ and you start from a permutation, you have to rule out adding the trhree additional 1's at $(i,j),(k,sigma(i)),(sigma^{-1}(j),sigma(k))$, besides the previous restrictions.
– san
Dec 14 '18 at 7:09