On a maximum of a determinant with dependent variables
Let $x_1,ldots,x_nin [-1,1]^n$ and define the function
$$f(x_1,ldots,x_n):= prod_{i=1}^nprod_{j=i}^nleft(1-prod_{k=i}^j x_kright).$$
This is a positive function, and actually coincides with the determinant of a $(n+1)times (n+1)$ matrix $M:=(a_{ij})_{i,j=1}^{n+1}$ where:
$$a_{i,i}=1, hspace{0.5cm}1leq ileq n+1,$$
$$a_{i+1,i}=1, hspace{0.5cm} i=1leq ileq n,$$
$$a_{i,j}=x_i^{j-1} cdot x_{i+1}^{j-i-1}cdots x_{j-1}, hspace{0.5cm}j>i,$$
$$a_{i,j}= x_{j+1}cdot x_{j+2}^2cdots x_{i-1}^{i-j-1}, hspace{0.5cm}j<i-1.$$
Thanks to the definition of $M$, we immediately get $fleq (n+1)^{(n+1)/2}$ by Hadamard's Lemma. But actually it is possible to get sharper estimates.
In 1977 M. Pohst https://www.sciencedirect.com/science/article/pii/0022314X77900075 proved
$$f(x_1,ldots,x_n)leq 2^{[(n+1)/2]}hspace{0.5cm}forall nleq 11,$$
where the brackets denote the floor integer part. His result was improved in 1996 by M. J. Bertin http://matwbn.icm.edu.pl/ksiazki/aa/aa74/aa7444.pdf who proved
$$f(x_1,ldots,x_n)leq 2^{[(n+1)/2]}hspace{0.5cm}forall n.$$
However, while I have no problems with Pohst's proof, I have some troubles with Bertin's one.
The key idea of her proof is the following: the maximum of the function $f$, seen as determinant of $M$, is estimated by the maximum of determinants of matrices similar to $M$ where the $x_i's$ are in ${-1,0,1}.$ In other words, the maximum is attained pushing the $x_i's$ to the boundary of their defining intervals.
My problem is that I am not convinced by this argument: I would agree that the maximum of the determinant is attained by pushing the elements of $M$ to the boundary if all these elements were independent of each other (the determinant would be an harmonic function of its variables). But this is not the case for $M$: once you have settled $x_1,ldots,x_n$ you immediately have all the remaining elements of the matrix.
Just look at the first line, formed by $1, x_1, x_1^2x_2, x_1^3x_2^2x_3$ and so on.
In the end, I do not get an exhaustive explanation of the estimate from the paper: is there some step or detail that I am missing? Any suggestion is well accepted.
linear-algebra optimization determinant
asked 2 days ago
F.BattistoniF.Battistoni
463
New contributor
F.Battistoni 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 |
Let $x_1,ldots,x_nin [-1,1]^n$ and define the function
$$f(x_1,ldots,x_n):= prod_{i=1}^nprod_{j=i}^nleft(1-prod_{k=i}^j x_kright).$$
This is a positive function, and actually coincides with the determinant of a $(n+1)times (n+1)$ matrix $M:=(a_{ij})_{i,j=1}^{n+1}$ where:
$$a_{i,i}=1, hspace{0.5cm}1leq ileq n+1,$$
$$a_{i+1,i}=1, hspace{0.5cm} i=1leq ileq n,$$
$$a_{i,j}=x_i^{j-1} cdot x_{i+1}^{j-i-1}cdots x_{j-1}, hspace{0.5cm}j>i,$$
$$a_{i,j}= x_{j+1}cdot x_{j+2}^2cdots x_{i-1}^{i-j-1}, hspace{0.5cm}j<i-1.$$
Thanks to the definition of $M$, we immediately get $fleq (n+1)^{(n+1)/2}$ by Hadamard's Lemma. But actually it is possible to get sharper estimates.
In 1977 M. Pohst https://www.sciencedirect.com/science/article/pii/0022314X77900075 proved
$$f(x_1,ldots,x_n)leq 2^{[(n+1)/2]}hspace{0.5cm}forall nleq 11,$$
where the brackets denote the floor integer part. His result was improved in 1996 by M. J. Bertin http://matwbn.icm.edu.pl/ksiazki/aa/aa74/aa7444.pdf who proved
$$f(x_1,ldots,x_n)leq 2^{[(n+1)/2]}hspace{0.5cm}forall n.$$
However, while I have no problems with Pohst's proof, I have some troubles with Bertin's one.
The key idea of her proof is the following: the maximum of the function $f$, seen as determinant of $M$, is estimated by the maximum of determinants of matrices similar to $M$ where the $x_i's$ are in ${-1,0,1}.$ In other words, the maximum is attained pushing the $x_i's$ to the boundary of their defining intervals.
My problem is that I am not convinced by this argument: I would agree that the maximum of the determinant is attained by pushing the elements of $M$ to the boundary if all these elements were independent of each other (the determinant would be an harmonic function of its variables). But this is not the case for $M$: once you have settled $x_1,ldots,x_n$ you immediately have all the remaining elements of the matrix.
Just look at the first line, formed by $1, x_1, x_1^2x_2, x_1^3x_2^2x_3$ and so on.
In the end, I do not get an exhaustive explanation of the estimate from the paper: is there some step or detail that I am missing? Any suggestion is well accepted.
linear-algebra optimization determinant
asked 2 days ago
F.BattistoniF.Battistoni
463
New contributor
F.Battistoni 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 |
Let $x_1,ldots,x_nin [-1,1]^n$ and define the function
$$f(x_1,ldots,x_n):= prod_{i=1}^nprod_{j=i}^nleft(1-prod_{k=i}^j x_kright).$$
This is a positive function, and actually coincides with the determinant of a $(n+1)times (n+1)$ matrix $M:=(a_{ij})_{i,j=1}^{n+1}$ where:
$$a_{i,i}=1, hspace{0.5cm}1leq ileq n+1,$$
$$a_{i+1,i}=1, hspace{0.5cm} i=1leq ileq n,$$
$$a_{i,j}=x_i^{j-1} cdot x_{i+1}^{j-i-1}cdots x_{j-1}, hspace{0.5cm}j>i,$$
$$a_{i,j}= x_{j+1}cdot x_{j+2}^2cdots x_{i-1}^{i-j-1}, hspace{0.5cm}j<i-1.$$
Thanks to the definition of $M$, we immediately get $fleq (n+1)^{(n+1)/2}$ by Hadamard's Lemma. But actually it is possible to get sharper estimates.
In 1977 M. Pohst https://www.sciencedirect.com/science/article/pii/0022314X77900075 proved
$$f(x_1,ldots,x_n)leq 2^{[(n+1)/2]}hspace{0.5cm}forall nleq 11,$$
where the brackets denote the floor integer part. His result was improved in 1996 by M. J. Bertin http://matwbn.icm.edu.pl/ksiazki/aa/aa74/aa7444.pdf who proved
$$f(x_1,ldots,x_n)leq 2^{[(n+1)/2]}hspace{0.5cm}forall n.$$
However, while I have no problems with Pohst's proof, I have some troubles with Bertin's one.
The key idea of her proof is the following: the maximum of the function $f$, seen as determinant of $M$, is estimated by the maximum of determinants of matrices similar to $M$ where the $x_i's$ are in ${-1,0,1}.$ In other words, the maximum is attained pushing the $x_i's$ to the boundary of their defining intervals.
My problem is that I am not convinced by this argument: I would agree that the maximum of the determinant is attained by pushing the elements of $M$ to the boundary if all these elements were independent of each other (the determinant would be an harmonic function of its variables). But this is not the case for $M$: once you have settled $x_1,ldots,x_n$ you immediately have all the remaining elements of the matrix.
Just look at the first line, formed by $1, x_1, x_1^2x_2, x_1^3x_2^2x_3$ and so on.
In the end, I do not get an exhaustive explanation of the estimate from the paper: is there some step or detail that I am missing? Any suggestion is well accepted.
linear-algebra optimization determinant
asked 2 days ago
F.BattistoniF.Battistoni
463
New contributor
F.Battistoni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Let $x_1,ldots,x_nin [-1,1]^n$ and define the function
$$f(x_1,ldots,x_n):= prod_{i=1}^nprod_{j=i}^nleft(1-prod_{k=i}^j x_kright).$$
This is a positive function, and actually coincides with the determinant of a $(n+1)times (n+1)$ matrix $M:=(a_{ij})_{i,j=1}^{n+1}$ where:
$$a_{i,i}=1, hspace{0.5cm}1leq ileq n+1,$$
$$a_{i+1,i}=1, hspace{0.5cm} i=1leq ileq n,$$
$$a_{i,j}=x_i^{j-1} cdot x_{i+1}^{j-i-1}cdots x_{j-1}, hspace{0.5cm}j>i,$$
$$a_{i,j}= x_{j+1}cdot x_{j+2}^2cdots x_{i-1}^{i-j-1}, hspace{0.5cm}j<i-1.$$
Thanks to the definition of $M$, we immediately get $fleq (n+1)^{(n+1)/2}$ by Hadamard's Lemma. But actually it is possible to get sharper estimates.
In 1977 M. Pohst https://www.sciencedirect.com/science/article/pii/0022314X77900075 proved
$$f(x_1,ldots,x_n)leq 2^{[(n+1)/2]}hspace{0.5cm}forall nleq 11,$$
where the brackets denote the floor integer part. His result was improved in 1996 by M. J. Bertin http://matwbn.icm.edu.pl/ksiazki/aa/aa74/aa7444.pdf who proved
$$f(x_1,ldots,x_n)leq 2^{[(n+1)/2]}hspace{0.5cm}forall n.$$
However, while I have no problems with Pohst's proof, I have some troubles with Bertin's one.
The key idea of her proof is the following: the maximum of the function $f$, seen as determinant of $M$, is estimated by the maximum of determinants of matrices similar to $M$ where the $x_i's$ are in ${-1,0,1}.$ In other words, the maximum is attained pushing the $x_i's$ to the boundary of their defining intervals.
My problem is that I am not convinced by this argument: I would agree that the maximum of the determinant is attained by pushing the elements of $M$ to the boundary if all these elements were independent of each other (the determinant would be an harmonic function of its variables). But this is not the case for $M$: once you have settled $x_1,ldots,x_n$ you immediately have all the remaining elements of the matrix.
Just look at the first line, formed by $1, x_1, x_1^2x_2, x_1^3x_2^2x_3$ and so on.
In the end, I do not get an exhaustive explanation of the estimate from the paper: is there some step or detail that I am missing? Any suggestion is well accepted.
linear-algebra optimization determinant
linear-algebra optimization determinant
asked 2 days ago
F.BattistoniF.Battistoni
463
New contributor
F.Battistoni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 days ago
F.BattistoniF.Battistoni
463
New contributor
F.Battistoni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 days ago
F.BattistoniF.Battistoni
463
New contributor
F.Battistoni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 days ago
F.BattistoniF.Battistoni
463
asked 2 days ago
F.BattistoniF.Battistoni
463
463
New contributor
F.Battistoni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
F.Battistoni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
F.Battistoni 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 |
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
});
}
});
F.Battistoni 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%2fmath.stackexchange.com%2fquestions%2f3062878%2fon-a-maximum-of-a-determinant-with-dependent-variables%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
F.Battistoni is a new contributor. Be nice, and check out our Code of Conduct.
F.Battistoni is a new contributor. Be nice, and check out our Code of Conduct.
F.Battistoni is a new contributor. Be nice, and check out our Code of Conduct.
F.Battistoni is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3062878%2fon-a-maximum-of-a-determinant-with-dependent-variables%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
