Determinant computation is equivalent to matrix powering
$begingroup$
It has been claimed in this paper (page 2 last paragraph) that Matrix powering is equivalent to determinant computation.
https://www.cse.iitk.ac.in/users/manindra/algebra/depth-four.pdf
Does anybody why is this the case?
complexity-theory matrices
asked 4 hours ago
grontimgrontim
1061
New contributor
grontim is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
It has been claimed in this paper (page 2 last paragraph) that Matrix powering is equivalent to determinant computation.
https://www.cse.iitk.ac.in/users/manindra/algebra/depth-four.pdf
Does anybody why is this the case?
complexity-theory matrices
asked 4 hours ago
grontimgrontim
1061
New contributor
grontim is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
It has been claimed in this paper (page 2 last paragraph) that Matrix powering is equivalent to determinant computation.
https://www.cse.iitk.ac.in/users/manindra/algebra/depth-four.pdf
Does anybody why is this the case?
complexity-theory matrices
asked 4 hours ago
grontimgrontim
1061
New contributor
grontim is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
It has been claimed in this paper (page 2 last paragraph) that Matrix powering is equivalent to determinant computation.
https://www.cse.iitk.ac.in/users/manindra/algebra/depth-four.pdf
Does anybody why is this the case?
complexity-theory matrices
complexity-theory matrices
asked 4 hours ago
grontimgrontim
1061
New contributor
grontim is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 4 hours ago
grontimgrontim
1061
New contributor
grontim is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 4 hours ago
grontimgrontim
1061
New contributor
grontim is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 4 hours ago
grontimgrontim
1061
asked 4 hours ago
grontimgrontim
1061
1061
New contributor
grontim is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
grontim is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
grontim is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
It states that matrix powering is computationaly equivalent to computation.
From another angle, Coppersmith–Winograd algorithm for matrix multiplication has complexity $mathcal O(n^{2.373})$ and the same complexity is for determinant computation by fast multiplication.
The result comes from Triangularization and inversion via fast multiplication by James R. Bunch and John E. Hopcroft
answered 3 hours ago
EvilEvil
7,78342446
$endgroup$
add a comment |
$begingroup$
Look at the paper by Stephen Cook (numbered $[3]$ in the references of the paper you have mentioned). There, in proposition $5.2$ in page $13$, he shows the "computational equivalence" between matrix powering and determinant computation (and other problems).
answered 3 hours ago
Don FanucciDon Fanucci
427311
$endgroup$
$begingroup$
Perhaps you should add the paper’s title, and if possible, a link.
$endgroup$
– Yuval Filmus
30 mins ago
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: "419"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
grontim is a new contributor. Be nice, and check out our Code of Conduct.
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%2fcs.stackexchange.com%2fquestions%2f104529%2fdeterminant-computation-is-equivalent-to-matrix-powering%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$
It states that matrix powering is computationaly equivalent to computation.
From another angle, Coppersmith–Winograd algorithm for matrix multiplication has complexity $mathcal O(n^{2.373})$ and the same complexity is for determinant computation by fast multiplication.
The result comes from Triangularization and inversion via fast multiplication by James R. Bunch and John E. Hopcroft
answered 3 hours ago
EvilEvil
7,78342446
$endgroup$
add a comment |
$begingroup$
It states that matrix powering is computationaly equivalent to computation.
From another angle, Coppersmith–Winograd algorithm for matrix multiplication has complexity $mathcal O(n^{2.373})$ and the same complexity is for determinant computation by fast multiplication.
The result comes from Triangularization and inversion via fast multiplication by James R. Bunch and John E. Hopcroft
answered 3 hours ago
EvilEvil
7,78342446
$endgroup$
add a comment |
$begingroup$
It states that matrix powering is computationaly equivalent to computation.
From another angle, Coppersmith–Winograd algorithm for matrix multiplication has complexity $mathcal O(n^{2.373})$ and the same complexity is for determinant computation by fast multiplication.
The result comes from Triangularization and inversion via fast multiplication by James R. Bunch and John E. Hopcroft
answered 3 hours ago
EvilEvil
7,78342446
$endgroup$
It states that matrix powering is computationaly equivalent to computation.
From another angle, Coppersmith–Winograd algorithm for matrix multiplication has complexity $mathcal O(n^{2.373})$ and the same complexity is for determinant computation by fast multiplication.
The result comes from Triangularization and inversion via fast multiplication by James R. Bunch and John E. Hopcroft
answered 3 hours ago
EvilEvil
7,78342446
edited 3 hours ago
answered 3 hours ago
EvilEvil
7,78342446
answered 3 hours ago
EvilEvil
7,78342446
answered 3 hours ago
EvilEvil
7,78342446
7,78342446
add a comment |
add a comment |
$begingroup$
Look at the paper by Stephen Cook (numbered $[3]$ in the references of the paper you have mentioned). There, in proposition $5.2$ in page $13$, he shows the "computational equivalence" between matrix powering and determinant computation (and other problems).
answered 3 hours ago
Don FanucciDon Fanucci
427311
$endgroup$
$begingroup$
Perhaps you should add the paper’s title, and if possible, a link.
$endgroup$
– Yuval Filmus
30 mins ago
add a comment |
$begingroup$
Look at the paper by Stephen Cook (numbered $[3]$ in the references of the paper you have mentioned). There, in proposition $5.2$ in page $13$, he shows the "computational equivalence" between matrix powering and determinant computation (and other problems).
answered 3 hours ago
Don FanucciDon Fanucci
427311
$endgroup$
$begingroup$
Perhaps you should add the paper’s title, and if possible, a link.
$endgroup$
– Yuval Filmus
30 mins ago
add a comment |
$begingroup$
Look at the paper by Stephen Cook (numbered $[3]$ in the references of the paper you have mentioned). There, in proposition $5.2$ in page $13$, he shows the "computational equivalence" between matrix powering and determinant computation (and other problems).
answered 3 hours ago
Don FanucciDon Fanucci
427311
$endgroup$
Look at the paper by Stephen Cook (numbered $[3]$ in the references of the paper you have mentioned). There, in proposition $5.2$ in page $13$, he shows the "computational equivalence" between matrix powering and determinant computation (and other problems).
answered 3 hours ago
Don FanucciDon Fanucci
427311
answered 3 hours ago
Don FanucciDon Fanucci
427311
answered 3 hours ago
Don FanucciDon Fanucci
427311
answered 3 hours ago
Don FanucciDon Fanucci
427311
427311
$begingroup$
Perhaps you should add the paper’s title, and if possible, a link.
$endgroup$
– Yuval Filmus
30 mins ago
add a comment |
$begingroup$
Perhaps you should add the paper’s title, and if possible, a link.
$endgroup$
– Yuval Filmus
30 mins ago
$begingroup$
Perhaps you should add the paper’s title, and if possible, a link.
$endgroup$
– Yuval Filmus
30 mins ago
$begingroup$
Perhaps you should add the paper’s title, and if possible, a link.
$endgroup$
– Yuval Filmus
30 mins ago
add a comment |
grontim is a new contributor. Be nice, and check out our Code of Conduct.
grontim is a new contributor. Be nice, and check out our Code of Conduct.
grontim is a new contributor. Be nice, and check out our Code of Conduct.
grontim is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Computer Science 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%2fcs.stackexchange.com%2fquestions%2f104529%2fdeterminant-computation-is-equivalent-to-matrix-powering%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
