On a maximum of a determinant with dependent variables
$begingroup$
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 Jan 5 at 16:19
F.BattistoniF.Battistoni
515
$endgroup$
add a comment |
$begingroup$
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 Jan 5 at 16:19
F.BattistoniF.Battistoni
515
$endgroup$
add a comment |
$begingroup$
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 Jan 5 at 16:19
F.BattistoniF.Battistoni
515
$endgroup$
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 Jan 5 at 16:19
F.BattistoniF.Battistoni
515
asked Jan 5 at 16:19
F.BattistoniF.Battistoni
515
asked Jan 5 at 16:19
F.BattistoniF.Battistoni
515
asked Jan 5 at 16:19
F.BattistoniF.Battistoni
515
asked Jan 5 at 16:19
F.BattistoniF.Battistoni
515
515
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
});
}
});
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
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.
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
