Hadamard product: Optimal bound on operator norm
$begingroup$
Let $A,B$ be $ntimes n $ matrices and denote by $Astar B$ the Hadamard product $(Astar B)(i,j)=A(i,j)B(i,j)$ (pointwise matrix multiplication). For $A$ positive definite it is known that
$$|Astar B| leq sup_{i,j} |A(i,j)| |B|.$$
My question is what happens if we drop the positive definiteness assumption, i.e. what is the best constant $C>0$ such that
$$|Astar B| leq C sup_{i,j} |A(i,j)| |B|$$
holds for arbitrary $ntimes n$ matrices $A,B$. Is the constant $C$ independent of the size of the matrix $n$?
linear-algebra matrices functional-analysis
asked Sep 6 '18 at 21:14
SanneSanne
485
$endgroup$
add a comment |
$begingroup$
Let $A,B$ be $ntimes n $ matrices and denote by $Astar B$ the Hadamard product $(Astar B)(i,j)=A(i,j)B(i,j)$ (pointwise matrix multiplication). For $A$ positive definite it is known that
$$|Astar B| leq sup_{i,j} |A(i,j)| |B|.$$
My question is what happens if we drop the positive definiteness assumption, i.e. what is the best constant $C>0$ such that
$$|Astar B| leq C sup_{i,j} |A(i,j)| |B|$$
holds for arbitrary $ntimes n$ matrices $A,B$. Is the constant $C$ independent of the size of the matrix $n$?
linear-algebra matrices functional-analysis
asked Sep 6 '18 at 21:14
SanneSanne
485
$endgroup$
add a comment |
$begingroup$
Let $A,B$ be $ntimes n $ matrices and denote by $Astar B$ the Hadamard product $(Astar B)(i,j)=A(i,j)B(i,j)$ (pointwise matrix multiplication). For $A$ positive definite it is known that
$$|Astar B| leq sup_{i,j} |A(i,j)| |B|.$$
My question is what happens if we drop the positive definiteness assumption, i.e. what is the best constant $C>0$ such that
$$|Astar B| leq C sup_{i,j} |A(i,j)| |B|$$
holds for arbitrary $ntimes n$ matrices $A,B$. Is the constant $C$ independent of the size of the matrix $n$?
linear-algebra matrices functional-analysis
asked Sep 6 '18 at 21:14
SanneSanne
485
$endgroup$
Let $A,B$ be $ntimes n $ matrices and denote by $Astar B$ the Hadamard product $(Astar B)(i,j)=A(i,j)B(i,j)$ (pointwise matrix multiplication). For $A$ positive definite it is known that
$$|Astar B| leq sup_{i,j} |A(i,j)| |B|.$$
My question is what happens if we drop the positive definiteness assumption, i.e. what is the best constant $C>0$ such that
$$|Astar B| leq C sup_{i,j} |A(i,j)| |B|$$
holds for arbitrary $ntimes n$ matrices $A,B$. Is the constant $C$ independent of the size of the matrix $n$?
linear-algebra matrices functional-analysis
linear-algebra matrices functional-analysis
asked Sep 6 '18 at 21:14
SanneSanne
485
asked Sep 6 '18 at 21:14
SanneSanne
485
asked Sep 6 '18 at 21:14
SanneSanne
485
asked Sep 6 '18 at 21:14
SanneSanne
485
asked Sep 6 '18 at 21:14
SanneSanne
485
485
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The optimal such $C$ is $sqrt{n}$, and so in particular there does not exist any such $C$ that is independent of $n$.
First, let me prove that $C=sqrt{n}$ works. Let $e_1,dots,e_n$ be the standard basis vectors, let $v=sum v_ie_i$ be any vector, and let $a=sup_{i,j}|A(i,j)|$. Note that for each $i$, $|(Astar B)e_i|leq a|B|$, since $|Be_i|leq |B|$ and $(Astar B)e_i$ is obtained from $Be_i$ by multiplying each entry by a scalar of size at most $a$. Thus $$|(Astar B)v|leqsum|v_i||(Astar B)e_i|leq a|B|sum|v_i|.$$ By Cauchy-Schwarz, $sum|v_i|leq sqrt{n}|v|$, so we conclude that $|Astar B|leq a|B|sqrt{n}$ and $C=sqrt{n}$ works.
To prove $C=sqrt{n}$ is optimal, let $omega$ be a primitive $n$th root of unity and let $B(i,j)=frac{omega^{ij}}{sqrt{n}}$. The columns of $B$ are orthonormal, so $B$ is unitary and $|B|=1$. Now let $A(i,j)=omega^{-ij}$, so that $Astar B$ is the matrix whose entries are all $frac{1}{sqrt{n}}$. We have $|Astar B|=sqrt{n}$ (the vector of all $1$s is an eigenvector of $Astar B$ with eigenvalue $sqrt{n}$). Since $|A(i,j)|=1$ for all $i,j$, this means we must have $Cgeq sqrt{n}$.
answered Sep 6 '18 at 22:24
Eric WofseyEric Wofsey
192k14217351
$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%2f2907991%2fhadamard-product-optimal-bound-on-operator-norm%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$
The optimal such $C$ is $sqrt{n}$, and so in particular there does not exist any such $C$ that is independent of $n$.
First, let me prove that $C=sqrt{n}$ works. Let $e_1,dots,e_n$ be the standard basis vectors, let $v=sum v_ie_i$ be any vector, and let $a=sup_{i,j}|A(i,j)|$. Note that for each $i$, $|(Astar B)e_i|leq a|B|$, since $|Be_i|leq |B|$ and $(Astar B)e_i$ is obtained from $Be_i$ by multiplying each entry by a scalar of size at most $a$. Thus $$|(Astar B)v|leqsum|v_i||(Astar B)e_i|leq a|B|sum|v_i|.$$ By Cauchy-Schwarz, $sum|v_i|leq sqrt{n}|v|$, so we conclude that $|Astar B|leq a|B|sqrt{n}$ and $C=sqrt{n}$ works.
To prove $C=sqrt{n}$ is optimal, let $omega$ be a primitive $n$th root of unity and let $B(i,j)=frac{omega^{ij}}{sqrt{n}}$. The columns of $B$ are orthonormal, so $B$ is unitary and $|B|=1$. Now let $A(i,j)=omega^{-ij}$, so that $Astar B$ is the matrix whose entries are all $frac{1}{sqrt{n}}$. We have $|Astar B|=sqrt{n}$ (the vector of all $1$s is an eigenvector of $Astar B$ with eigenvalue $sqrt{n}$). Since $|A(i,j)|=1$ for all $i,j$, this means we must have $Cgeq sqrt{n}$.
answered Sep 6 '18 at 22:24
Eric WofseyEric Wofsey
192k14217351
$endgroup$
add a comment |
$begingroup$
The optimal such $C$ is $sqrt{n}$, and so in particular there does not exist any such $C$ that is independent of $n$.
First, let me prove that $C=sqrt{n}$ works. Let $e_1,dots,e_n$ be the standard basis vectors, let $v=sum v_ie_i$ be any vector, and let $a=sup_{i,j}|A(i,j)|$. Note that for each $i$, $|(Astar B)e_i|leq a|B|$, since $|Be_i|leq |B|$ and $(Astar B)e_i$ is obtained from $Be_i$ by multiplying each entry by a scalar of size at most $a$. Thus $$|(Astar B)v|leqsum|v_i||(Astar B)e_i|leq a|B|sum|v_i|.$$ By Cauchy-Schwarz, $sum|v_i|leq sqrt{n}|v|$, so we conclude that $|Astar B|leq a|B|sqrt{n}$ and $C=sqrt{n}$ works.
To prove $C=sqrt{n}$ is optimal, let $omega$ be a primitive $n$th root of unity and let $B(i,j)=frac{omega^{ij}}{sqrt{n}}$. The columns of $B$ are orthonormal, so $B$ is unitary and $|B|=1$. Now let $A(i,j)=omega^{-ij}$, so that $Astar B$ is the matrix whose entries are all $frac{1}{sqrt{n}}$. We have $|Astar B|=sqrt{n}$ (the vector of all $1$s is an eigenvector of $Astar B$ with eigenvalue $sqrt{n}$). Since $|A(i,j)|=1$ for all $i,j$, this means we must have $Cgeq sqrt{n}$.
answered Sep 6 '18 at 22:24
Eric WofseyEric Wofsey
192k14217351
$endgroup$
add a comment |
$begingroup$
The optimal such $C$ is $sqrt{n}$, and so in particular there does not exist any such $C$ that is independent of $n$.
First, let me prove that $C=sqrt{n}$ works. Let $e_1,dots,e_n$ be the standard basis vectors, let $v=sum v_ie_i$ be any vector, and let $a=sup_{i,j}|A(i,j)|$. Note that for each $i$, $|(Astar B)e_i|leq a|B|$, since $|Be_i|leq |B|$ and $(Astar B)e_i$ is obtained from $Be_i$ by multiplying each entry by a scalar of size at most $a$. Thus $$|(Astar B)v|leqsum|v_i||(Astar B)e_i|leq a|B|sum|v_i|.$$ By Cauchy-Schwarz, $sum|v_i|leq sqrt{n}|v|$, so we conclude that $|Astar B|leq a|B|sqrt{n}$ and $C=sqrt{n}$ works.
To prove $C=sqrt{n}$ is optimal, let $omega$ be a primitive $n$th root of unity and let $B(i,j)=frac{omega^{ij}}{sqrt{n}}$. The columns of $B$ are orthonormal, so $B$ is unitary and $|B|=1$. Now let $A(i,j)=omega^{-ij}$, so that $Astar B$ is the matrix whose entries are all $frac{1}{sqrt{n}}$. We have $|Astar B|=sqrt{n}$ (the vector of all $1$s is an eigenvector of $Astar B$ with eigenvalue $sqrt{n}$). Since $|A(i,j)|=1$ for all $i,j$, this means we must have $Cgeq sqrt{n}$.
answered Sep 6 '18 at 22:24
Eric WofseyEric Wofsey
192k14217351
$endgroup$
The optimal such $C$ is $sqrt{n}$, and so in particular there does not exist any such $C$ that is independent of $n$.
First, let me prove that $C=sqrt{n}$ works. Let $e_1,dots,e_n$ be the standard basis vectors, let $v=sum v_ie_i$ be any vector, and let $a=sup_{i,j}|A(i,j)|$. Note that for each $i$, $|(Astar B)e_i|leq a|B|$, since $|Be_i|leq |B|$ and $(Astar B)e_i$ is obtained from $Be_i$ by multiplying each entry by a scalar of size at most $a$. Thus $$|(Astar B)v|leqsum|v_i||(Astar B)e_i|leq a|B|sum|v_i|.$$ By Cauchy-Schwarz, $sum|v_i|leq sqrt{n}|v|$, so we conclude that $|Astar B|leq a|B|sqrt{n}$ and $C=sqrt{n}$ works.
To prove $C=sqrt{n}$ is optimal, let $omega$ be a primitive $n$th root of unity and let $B(i,j)=frac{omega^{ij}}{sqrt{n}}$. The columns of $B$ are orthonormal, so $B$ is unitary and $|B|=1$. Now let $A(i,j)=omega^{-ij}$, so that $Astar B$ is the matrix whose entries are all $frac{1}{sqrt{n}}$. We have $|Astar B|=sqrt{n}$ (the vector of all $1$s is an eigenvector of $Astar B$ with eigenvalue $sqrt{n}$). Since $|A(i,j)|=1$ for all $i,j$, this means we must have $Cgeq sqrt{n}$.
answered Sep 6 '18 at 22:24
Eric WofseyEric Wofsey
192k14217351
edited Jan 4 at 6:11
answered Sep 6 '18 at 22:24
Eric WofseyEric Wofsey
192k14217351
answered Sep 6 '18 at 22:24
Eric WofseyEric Wofsey
192k14217351
answered Sep 6 '18 at 22:24
Eric WofseyEric Wofsey
192k14217351
192k14217351
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%2f2907991%2fhadamard-product-optimal-bound-on-operator-norm%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
