Determinants of binary matrices
$begingroup$
I was surprised to find that most $3times 3$ matrices with entries in ${0,1}$ have determinant $0$ or $pm 1$. There are only six out of 512 matrices with a different determinant (three with $2$ and three with $-2$) and these are
$$
begin{bmatrix}1 & 1 & 0\ 0 & 1 & 1\ 1 & 0 & 1end{bmatrix}
$$
and the different permutation of this.
Hadamard's maximum determinant problem for ${0,1}$ asks about the largest possible determinant for matrices with entries in ${0,1}$ and it is known that the sequence of the maximal determinant for $ntimes n$ matrices for $n=1,2,dots$ starts with 1, 1, 2, 3, 5, 9, 32, 56, 144, 320,1458 (https://oeis.org/A003432). It is even known that the number of different matrices realizing the maximum (not by absolute value) is 1, 3, 3, 60, 3600, 529200, 75600, 195955200, (https://oeis.org/A051752).
My question is: what is the distribution of determinants of all $ntimes n$ ${0,1}$-matrices?
Here is the data for (very) small $n$:
$$
begin{array}{lccccccc}
n & -3 & -2 & -1 & 0 & 1 & 2 & 3\hline
1 & & & & 1 & & & \
2 & & & 3 &10 & 3 & & \
3 & & 3 & 84 & 338 & 84 & 3 & \
4 & 60 & 1200 & 10020 & 42976 & 10020 & 1200 & 60
end{array}
$$
linear-algebra determinants
asked 7 hours ago
DirkDirk
7,39143267
$endgroup$
add a comment |
$begingroup$
I was surprised to find that most $3times 3$ matrices with entries in ${0,1}$ have determinant $0$ or $pm 1$. There are only six out of 512 matrices with a different determinant (three with $2$ and three with $-2$) and these are
$$
begin{bmatrix}1 & 1 & 0\ 0 & 1 & 1\ 1 & 0 & 1end{bmatrix}
$$
and the different permutation of this.
Hadamard's maximum determinant problem for ${0,1}$ asks about the largest possible determinant for matrices with entries in ${0,1}$ and it is known that the sequence of the maximal determinant for $ntimes n$ matrices for $n=1,2,dots$ starts with 1, 1, 2, 3, 5, 9, 32, 56, 144, 320,1458 (https://oeis.org/A003432). It is even known that the number of different matrices realizing the maximum (not by absolute value) is 1, 3, 3, 60, 3600, 529200, 75600, 195955200, (https://oeis.org/A051752).
My question is: what is the distribution of determinants of all $ntimes n$ ${0,1}$-matrices?
Here is the data for (very) small $n$:
$$
begin{array}{lccccccc}
n & -3 & -2 & -1 & 0 & 1 & 2 & 3\hline
1 & & & & 1 & & & \
2 & & & 3 &10 & 3 & & \
3 & & 3 & 84 & 338 & 84 & 3 & \
4 & 60 & 1200 & 10020 & 42976 & 10020 & 1200 & 60
end{array}
$$
linear-algebra determinants
asked 7 hours ago
DirkDirk
7,39143267
$endgroup$
3
$begingroup$
Will Orrick probably has the latest data. Miodrag Zivkovic did an analysis in 2005 for n up to 9. While lower determinant values are heavily weighted, it is not known how quickly the counts for off as the determinant value grows. You can find related questions here on MathOverflow. Gerhard "Search For Determinant Spectrum Problem" Paseman, 2019.01.15.
$endgroup$
– Gerhard Paseman
6 hours ago
$begingroup$
Related MO questions: mathoverflow.net/questions/18636/… mathoverflow.net/questions/18547/… mathoverflow.net/questions/39786/…
$endgroup$
– Timothy Chow
13 mins ago
add a comment |
$begingroup$
I was surprised to find that most $3times 3$ matrices with entries in ${0,1}$ have determinant $0$ or $pm 1$. There are only six out of 512 matrices with a different determinant (three with $2$ and three with $-2$) and these are
$$
begin{bmatrix}1 & 1 & 0\ 0 & 1 & 1\ 1 & 0 & 1end{bmatrix}
$$
and the different permutation of this.
Hadamard's maximum determinant problem for ${0,1}$ asks about the largest possible determinant for matrices with entries in ${0,1}$ and it is known that the sequence of the maximal determinant for $ntimes n$ matrices for $n=1,2,dots$ starts with 1, 1, 2, 3, 5, 9, 32, 56, 144, 320,1458 (https://oeis.org/A003432). It is even known that the number of different matrices realizing the maximum (not by absolute value) is 1, 3, 3, 60, 3600, 529200, 75600, 195955200, (https://oeis.org/A051752).
My question is: what is the distribution of determinants of all $ntimes n$ ${0,1}$-matrices?
Here is the data for (very) small $n$:
$$
begin{array}{lccccccc}
n & -3 & -2 & -1 & 0 & 1 & 2 & 3\hline
1 & & & & 1 & & & \
2 & & & 3 &10 & 3 & & \
3 & & 3 & 84 & 338 & 84 & 3 & \
4 & 60 & 1200 & 10020 & 42976 & 10020 & 1200 & 60
end{array}
$$
linear-algebra determinants
asked 7 hours ago
DirkDirk
7,39143267
$endgroup$
I was surprised to find that most $3times 3$ matrices with entries in ${0,1}$ have determinant $0$ or $pm 1$. There are only six out of 512 matrices with a different determinant (three with $2$ and three with $-2$) and these are
$$
begin{bmatrix}1 & 1 & 0\ 0 & 1 & 1\ 1 & 0 & 1end{bmatrix}
$$
and the different permutation of this.
Hadamard's maximum determinant problem for ${0,1}$ asks about the largest possible determinant for matrices with entries in ${0,1}$ and it is known that the sequence of the maximal determinant for $ntimes n$ matrices for $n=1,2,dots$ starts with 1, 1, 2, 3, 5, 9, 32, 56, 144, 320,1458 (https://oeis.org/A003432). It is even known that the number of different matrices realizing the maximum (not by absolute value) is 1, 3, 3, 60, 3600, 529200, 75600, 195955200, (https://oeis.org/A051752).
My question is: what is the distribution of determinants of all $ntimes n$ ${0,1}$-matrices?
Here is the data for (very) small $n$:
$$
begin{array}{lccccccc}
n & -3 & -2 & -1 & 0 & 1 & 2 & 3\hline
1 & & & & 1 & & & \
2 & & & 3 &10 & 3 & & \
3 & & 3 & 84 & 338 & 84 & 3 & \
4 & 60 & 1200 & 10020 & 42976 & 10020 & 1200 & 60
end{array}
$$
linear-algebra determinants
linear-algebra determinants
asked 7 hours ago
DirkDirk
7,39143267
asked 7 hours ago
DirkDirk
7,39143267
edited 6 hours ago
Dirk
asked 7 hours ago
DirkDirk
7,39143267
asked 7 hours ago
DirkDirk
7,39143267
asked 7 hours ago
DirkDirk
7,39143267
7,39143267
3
$begingroup$
Will Orrick probably has the latest data. Miodrag Zivkovic did an analysis in 2005 for n up to 9. While lower determinant values are heavily weighted, it is not known how quickly the counts for off as the determinant value grows. You can find related questions here on MathOverflow. Gerhard "Search For Determinant Spectrum Problem" Paseman, 2019.01.15.
$endgroup$
– Gerhard Paseman
6 hours ago
$begingroup$
Related MO questions: mathoverflow.net/questions/18636/… mathoverflow.net/questions/18547/… mathoverflow.net/questions/39786/…
$endgroup$
– Timothy Chow
13 mins ago
add a comment |
3
$begingroup$
Will Orrick probably has the latest data. Miodrag Zivkovic did an analysis in 2005 for n up to 9. While lower determinant values are heavily weighted, it is not known how quickly the counts for off as the determinant value grows. You can find related questions here on MathOverflow. Gerhard "Search For Determinant Spectrum Problem" Paseman, 2019.01.15.
$endgroup$
– Gerhard Paseman
6 hours ago
$begingroup$
Related MO questions: mathoverflow.net/questions/18636/… mathoverflow.net/questions/18547/… mathoverflow.net/questions/39786/…
$endgroup$
– Timothy Chow
13 mins ago
3
3
$begingroup$
Will Orrick probably has the latest data. Miodrag Zivkovic did an analysis in 2005 for n up to 9. While lower determinant values are heavily weighted, it is not known how quickly the counts for off as the determinant value grows. You can find related questions here on MathOverflow. Gerhard "Search For Determinant Spectrum Problem" Paseman, 2019.01.15.
$endgroup$
– Gerhard Paseman
6 hours ago
$begingroup$
Will Orrick probably has the latest data. Miodrag Zivkovic did an analysis in 2005 for n up to 9. While lower determinant values are heavily weighted, it is not known how quickly the counts for off as the determinant value grows. You can find related questions here on MathOverflow. Gerhard "Search For Determinant Spectrum Problem" Paseman, 2019.01.15.
$endgroup$
– Gerhard Paseman
6 hours ago
$begingroup$
Related MO questions: mathoverflow.net/questions/18636/… mathoverflow.net/questions/18547/… mathoverflow.net/questions/39786/…
$endgroup$
– Timothy Chow
13 mins ago
$begingroup$
Related MO questions: mathoverflow.net/questions/18636/… mathoverflow.net/questions/18547/… mathoverflow.net/questions/39786/…
$endgroup$
– Timothy Chow
13 mins ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
This question is too hard, because easier questions are already known to be hard.
The middle column is A046747 in the OEIS, which is essentially equivalent to A057982, the number of singular {±1}-valued matrices. The asymptotic behavior of this number was a longstanding open problem that was just recently solved by Tikhomirov.
As you mentioned yourself, the Hadamard maximal determinant problem is unsolved, with order 15 (for the {±1} version of the problem) being difficult already. The determinant spectrum problem, mentioned by Gerhard Paseman, is even harder, and is easier than your question, since it's just asking for which values are zero.
answered 4 hours ago
Timothy ChowTimothy Chow
34.5k11183309
$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: "504"
};
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%2fmathoverflow.net%2fquestions%2f320965%2fdeterminants-of-binary-matrices%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
$begingroup$
This question is too hard, because easier questions are already known to be hard.
The middle column is A046747 in the OEIS, which is essentially equivalent to A057982, the number of singular {±1}-valued matrices. The asymptotic behavior of this number was a longstanding open problem that was just recently solved by Tikhomirov.
As you mentioned yourself, the Hadamard maximal determinant problem is unsolved, with order 15 (for the {±1} version of the problem) being difficult already. The determinant spectrum problem, mentioned by Gerhard Paseman, is even harder, and is easier than your question, since it's just asking for which values are zero.
answered 4 hours ago
Timothy ChowTimothy Chow
34.5k11183309
$endgroup$
add a comment |
$begingroup$
This question is too hard, because easier questions are already known to be hard.
The middle column is A046747 in the OEIS, which is essentially equivalent to A057982, the number of singular {±1}-valued matrices. The asymptotic behavior of this number was a longstanding open problem that was just recently solved by Tikhomirov.
As you mentioned yourself, the Hadamard maximal determinant problem is unsolved, with order 15 (for the {±1} version of the problem) being difficult already. The determinant spectrum problem, mentioned by Gerhard Paseman, is even harder, and is easier than your question, since it's just asking for which values are zero.
answered 4 hours ago
Timothy ChowTimothy Chow
34.5k11183309
$endgroup$
add a comment |
$begingroup$
This question is too hard, because easier questions are already known to be hard.
The middle column is A046747 in the OEIS, which is essentially equivalent to A057982, the number of singular {±1}-valued matrices. The asymptotic behavior of this number was a longstanding open problem that was just recently solved by Tikhomirov.
As you mentioned yourself, the Hadamard maximal determinant problem is unsolved, with order 15 (for the {±1} version of the problem) being difficult already. The determinant spectrum problem, mentioned by Gerhard Paseman, is even harder, and is easier than your question, since it's just asking for which values are zero.
answered 4 hours ago
Timothy ChowTimothy Chow
34.5k11183309
$endgroup$
This question is too hard, because easier questions are already known to be hard.
The middle column is A046747 in the OEIS, which is essentially equivalent to A057982, the number of singular {±1}-valued matrices. The asymptotic behavior of this number was a longstanding open problem that was just recently solved by Tikhomirov.
As you mentioned yourself, the Hadamard maximal determinant problem is unsolved, with order 15 (for the {±1} version of the problem) being difficult already. The determinant spectrum problem, mentioned by Gerhard Paseman, is even harder, and is easier than your question, since it's just asking for which values are zero.
answered 4 hours ago
Timothy ChowTimothy Chow
34.5k11183309
answered 4 hours ago
Timothy ChowTimothy Chow
34.5k11183309
answered 4 hours ago
Timothy ChowTimothy Chow
34.5k11183309
answered 4 hours ago
Timothy ChowTimothy Chow
34.5k11183309
34.5k11183309
add a comment |
add a comment |
Thanks for contributing an answer to MathOverflow!
- 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%2fmathoverflow.net%2fquestions%2f320965%2fdeterminants-of-binary-matrices%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
$begingroup$
Will Orrick probably has the latest data. Miodrag Zivkovic did an analysis in 2005 for n up to 9. While lower determinant values are heavily weighted, it is not known how quickly the counts for off as the determinant value grows. You can find related questions here on MathOverflow. Gerhard "Search For Determinant Spectrum Problem" Paseman, 2019.01.15.
$endgroup$
– Gerhard Paseman
6 hours ago
$begingroup$
Related MO questions: mathoverflow.net/questions/18636/… mathoverflow.net/questions/18547/… mathoverflow.net/questions/39786/…
$endgroup$
– Timothy Chow
13 mins ago