Mixing
Bounding the determinant of a matrix with bounded coefficients
$begingroup$
Suppose that $A$ is a real matrix of dimension $n times n$ and that its coefficients are bounded by $cge0$ ($vert a_{ij} vert le c$ for all $1le i,j le n$).
How to prove that
$$vert det A vert le c^n n^{n/2}$$
matrices determinant
asked Jan 19 at 21:27
mathcounterexamples.netmathcounterexamples.net
27k22157
$endgroup$
add a comment |
$begingroup$
Suppose that $A$ is a real matrix of dimension $n times n$ and that its coefficients are bounded by $cge0$ ($vert a_{ij} vert le c$ for all $1le i,j le n$).
How to prove that
$$vert det A vert le c^n n^{n/2}$$
matrices determinant
asked Jan 19 at 21:27
mathcounterexamples.netmathcounterexamples.net
27k22157
$endgroup$
1
$begingroup$
Hint: Look at the determinant of the product of the matrix with its transpose.
$endgroup$
– Somos
Jan 19 at 21:38
add a comment |
$begingroup$
Suppose that $A$ is a real matrix of dimension $n times n$ and that its coefficients are bounded by $cge0$ ($vert a_{ij} vert le c$ for all $1le i,j le n$).
How to prove that
$$vert det A vert le c^n n^{n/2}$$
matrices determinant
asked Jan 19 at 21:27
mathcounterexamples.netmathcounterexamples.net
27k22157
$endgroup$
Suppose that $A$ is a real matrix of dimension $n times n$ and that its coefficients are bounded by $cge0$ ($vert a_{ij} vert le c$ for all $1le i,j le n$).
How to prove that
$$vert det A vert le c^n n^{n/2}$$
matrices determinant
matrices determinant
asked Jan 19 at 21:27
mathcounterexamples.netmathcounterexamples.net
27k22157
asked Jan 19 at 21:27
mathcounterexamples.netmathcounterexamples.net
27k22157
asked Jan 19 at 21:27
mathcounterexamples.netmathcounterexamples.net
27k22157
asked Jan 19 at 21:27
mathcounterexamples.netmathcounterexamples.net
27k22157
asked Jan 19 at 21:27
mathcounterexamples.netmathcounterexamples.net
27k22157
27k22157
1
$begingroup$
Hint: Look at the determinant of the product of the matrix with its transpose.
$endgroup$
– Somos
Jan 19 at 21:38
add a comment |
1
$begingroup$
Hint: Look at the determinant of the product of the matrix with its transpose.
$endgroup$
– Somos
Jan 19 at 21:38
1
1
$begingroup$
Hint: Look at the determinant of the product of the matrix with its transpose.
$endgroup$
– Somos
Jan 19 at 21:38
$begingroup$
Hint: Look at the determinant of the product of the matrix with its transpose.
$endgroup$
– Somos
Jan 19 at 21:38
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
If we consider $A/c$, we see that it is equivalent to show that for $c = 1$, we have $det(A) leq n^{n/2}$. Moreover, since $|det(A)| = sqrt{det(A^TA)}$, it suffices to note that $det(A^TA) leq n^n$.
With this in mind, suppose that $A$ is such that $|a_{ij}| leq 1$. We note that $M = A^TA$ satisfies
$$
|M_{ij}| = left|sum_{k=1}^n a_{ik}a_{kj}right| leq sum_{k=1}^n |a_{ik}| ,|a_{kj}| leq sum_{k=1}^n 1 = n
$$
Moreover, $M$ is symmetric positive definite. Let $lambda_i$ denote the eigenvalues of $M$. We have
$$
operatorname{tr}(M) = sum_i lambda_i = sum_{i} M_{ii} leq n^2
$$
Now, consider the problem of maximizing $prod_{i=1}^n lambda_i$ under the constraint that we have $lambda_i geq 0$ and $sum lambda_i leq n^2$. We find that this product is maximized when
$$
lambda_1 = cdots = lambda_n = n^2/n = n
$$
for a maximum product of $n^n$. Or, if you prefer, the AM-GM inequality tells us that
$$
prod_{i=1}^n lambda_i = left(left[prod_{i=1}^n lambda_iright]^{1/n}right)^n leq
left(left[sum_{i=1}^n lambda_i/nright]right)^n leq n^n
$$
Thus, it follows that
$$
det(A^TA) = det(M) = prod_{i=1}^n lambda_i leq n^n
$$
As was desired.
answered Jan 19 at 22:01
OmnomnomnomOmnomnomnom
128k791185
$endgroup$
add a comment |
$begingroup$
Since
is ture for every element in the matrix, let us consider a matrix where all of the coefficients are the value of c.
Now factor out the c throughout the entire matrix.
Using a formula we obtain
Which reduces to
Using another formula
Reduces to
Since all elements in the matrix where of value c then all of the elements left are valued as 1. The result will be that the determinant of a matrix times a matrix transpose will be zero.
answered Jan 20 at 2:03
Erock BroxErock Brox
23628
$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: "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%2f3079857%2fbounding-the-determinant-of-a-matrix-with-bounded-coefficients%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$
If we consider $A/c$, we see that it is equivalent to show that for $c = 1$, we have $det(A) leq n^{n/2}$. Moreover, since $|det(A)| = sqrt{det(A^TA)}$, it suffices to note that $det(A^TA) leq n^n$.
With this in mind, suppose that $A$ is such that $|a_{ij}| leq 1$. We note that $M = A^TA$ satisfies
$$
|M_{ij}| = left|sum_{k=1}^n a_{ik}a_{kj}right| leq sum_{k=1}^n |a_{ik}| ,|a_{kj}| leq sum_{k=1}^n 1 = n
$$
Moreover, $M$ is symmetric positive definite. Let $lambda_i$ denote the eigenvalues of $M$. We have
$$
operatorname{tr}(M) = sum_i lambda_i = sum_{i} M_{ii} leq n^2
$$
Now, consider the problem of maximizing $prod_{i=1}^n lambda_i$ under the constraint that we have $lambda_i geq 0$ and $sum lambda_i leq n^2$. We find that this product is maximized when
$$
lambda_1 = cdots = lambda_n = n^2/n = n
$$
for a maximum product of $n^n$. Or, if you prefer, the AM-GM inequality tells us that
$$
prod_{i=1}^n lambda_i = left(left[prod_{i=1}^n lambda_iright]^{1/n}right)^n leq
left(left[sum_{i=1}^n lambda_i/nright]right)^n leq n^n
$$
Thus, it follows that
$$
det(A^TA) = det(M) = prod_{i=1}^n lambda_i leq n^n
$$
As was desired.
answered Jan 19 at 22:01
OmnomnomnomOmnomnomnom
128k791185
$endgroup$
add a comment |
$begingroup$
If we consider $A/c$, we see that it is equivalent to show that for $c = 1$, we have $det(A) leq n^{n/2}$. Moreover, since $|det(A)| = sqrt{det(A^TA)}$, it suffices to note that $det(A^TA) leq n^n$.
With this in mind, suppose that $A$ is such that $|a_{ij}| leq 1$. We note that $M = A^TA$ satisfies
$$
|M_{ij}| = left|sum_{k=1}^n a_{ik}a_{kj}right| leq sum_{k=1}^n |a_{ik}| ,|a_{kj}| leq sum_{k=1}^n 1 = n
$$
Moreover, $M$ is symmetric positive definite. Let $lambda_i$ denote the eigenvalues of $M$. We have
$$
operatorname{tr}(M) = sum_i lambda_i = sum_{i} M_{ii} leq n^2
$$
Now, consider the problem of maximizing $prod_{i=1}^n lambda_i$ under the constraint that we have $lambda_i geq 0$ and $sum lambda_i leq n^2$. We find that this product is maximized when
$$
lambda_1 = cdots = lambda_n = n^2/n = n
$$
for a maximum product of $n^n$. Or, if you prefer, the AM-GM inequality tells us that
$$
prod_{i=1}^n lambda_i = left(left[prod_{i=1}^n lambda_iright]^{1/n}right)^n leq
left(left[sum_{i=1}^n lambda_i/nright]right)^n leq n^n
$$
Thus, it follows that
$$
det(A^TA) = det(M) = prod_{i=1}^n lambda_i leq n^n
$$
As was desired.
answered Jan 19 at 22:01
OmnomnomnomOmnomnomnom
128k791185
$endgroup$
add a comment |
$begingroup$
If we consider $A/c$, we see that it is equivalent to show that for $c = 1$, we have $det(A) leq n^{n/2}$. Moreover, since $|det(A)| = sqrt{det(A^TA)}$, it suffices to note that $det(A^TA) leq n^n$.
With this in mind, suppose that $A$ is such that $|a_{ij}| leq 1$. We note that $M = A^TA$ satisfies
$$
|M_{ij}| = left|sum_{k=1}^n a_{ik}a_{kj}right| leq sum_{k=1}^n |a_{ik}| ,|a_{kj}| leq sum_{k=1}^n 1 = n
$$
Moreover, $M$ is symmetric positive definite. Let $lambda_i$ denote the eigenvalues of $M$. We have
$$
operatorname{tr}(M) = sum_i lambda_i = sum_{i} M_{ii} leq n^2
$$
Now, consider the problem of maximizing $prod_{i=1}^n lambda_i$ under the constraint that we have $lambda_i geq 0$ and $sum lambda_i leq n^2$. We find that this product is maximized when
$$
lambda_1 = cdots = lambda_n = n^2/n = n
$$
for a maximum product of $n^n$. Or, if you prefer, the AM-GM inequality tells us that
$$
prod_{i=1}^n lambda_i = left(left[prod_{i=1}^n lambda_iright]^{1/n}right)^n leq
left(left[sum_{i=1}^n lambda_i/nright]right)^n leq n^n
$$
Thus, it follows that
$$
det(A^TA) = det(M) = prod_{i=1}^n lambda_i leq n^n
$$
As was desired.
answered Jan 19 at 22:01
OmnomnomnomOmnomnomnom
128k791185
$endgroup$
If we consider $A/c$, we see that it is equivalent to show that for $c = 1$, we have $det(A) leq n^{n/2}$. Moreover, since $|det(A)| = sqrt{det(A^TA)}$, it suffices to note that $det(A^TA) leq n^n$.
With this in mind, suppose that $A$ is such that $|a_{ij}| leq 1$. We note that $M = A^TA$ satisfies
$$
|M_{ij}| = left|sum_{k=1}^n a_{ik}a_{kj}right| leq sum_{k=1}^n |a_{ik}| ,|a_{kj}| leq sum_{k=1}^n 1 = n
$$
Moreover, $M$ is symmetric positive definite. Let $lambda_i$ denote the eigenvalues of $M$. We have
$$
operatorname{tr}(M) = sum_i lambda_i = sum_{i} M_{ii} leq n^2
$$
Now, consider the problem of maximizing $prod_{i=1}^n lambda_i$ under the constraint that we have $lambda_i geq 0$ and $sum lambda_i leq n^2$. We find that this product is maximized when
$$
lambda_1 = cdots = lambda_n = n^2/n = n
$$
for a maximum product of $n^n$. Or, if you prefer, the AM-GM inequality tells us that
$$
prod_{i=1}^n lambda_i = left(left[prod_{i=1}^n lambda_iright]^{1/n}right)^n leq
left(left[sum_{i=1}^n lambda_i/nright]right)^n leq n^n
$$
Thus, it follows that
$$
det(A^TA) = det(M) = prod_{i=1}^n lambda_i leq n^n
$$
As was desired.
answered Jan 19 at 22:01
OmnomnomnomOmnomnomnom
128k791185
edited Jan 19 at 22:07
answered Jan 19 at 22:01
OmnomnomnomOmnomnomnom
128k791185
answered Jan 19 at 22:01
OmnomnomnomOmnomnomnom
128k791185
answered Jan 19 at 22:01
OmnomnomnomOmnomnomnom
128k791185
128k791185
add a comment |
add a comment |
$begingroup$
Since
is ture for every element in the matrix, let us consider a matrix where all of the coefficients are the value of c.
Now factor out the c throughout the entire matrix.
Using a formula we obtain
Which reduces to
Using another formula
Reduces to
Since all elements in the matrix where of value c then all of the elements left are valued as 1. The result will be that the determinant of a matrix times a matrix transpose will be zero.
answered Jan 20 at 2:03
Erock BroxErock Brox
23628
$endgroup$
add a comment |
$begingroup$
Since
is ture for every element in the matrix, let us consider a matrix where all of the coefficients are the value of c.
Now factor out the c throughout the entire matrix.
Using a formula we obtain
Which reduces to
Using another formula
Reduces to
Since all elements in the matrix where of value c then all of the elements left are valued as 1. The result will be that the determinant of a matrix times a matrix transpose will be zero.
answered Jan 20 at 2:03
Erock BroxErock Brox
23628
$endgroup$
add a comment |
$begingroup$
Since
is ture for every element in the matrix, let us consider a matrix where all of the coefficients are the value of c.
Now factor out the c throughout the entire matrix.
Using a formula we obtain
Which reduces to
Using another formula
Reduces to
Since all elements in the matrix where of value c then all of the elements left are valued as 1. The result will be that the determinant of a matrix times a matrix transpose will be zero.
answered Jan 20 at 2:03
Erock BroxErock Brox
23628
$endgroup$
Since
is ture for every element in the matrix, let us consider a matrix where all of the coefficients are the value of c.
Now factor out the c throughout the entire matrix.
Using a formula we obtain
Which reduces to
Using another formula
Reduces to
Since all elements in the matrix where of value c then all of the elements left are valued as 1. The result will be that the determinant of a matrix times a matrix transpose will be zero.
answered Jan 20 at 2:03
Erock BroxErock Brox
23628
answered Jan 20 at 2:03
Erock BroxErock Brox
23628
answered Jan 20 at 2:03
Erock BroxErock Brox
23628
answered Jan 20 at 2:03
Erock BroxErock Brox
23628
23628
add a comment |
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.
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%2f3079857%2fbounding-the-determinant-of-a-matrix-with-bounded-coefficients%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
1
$begingroup$
Hint: Look at the determinant of the product of the matrix with its transpose.
$endgroup$
– Somos
Jan 19 at 21:38