Relation between Frobenius, spectral norm and sum of maxima












4












$begingroup$


Let $A$ be a $n times n$ matrix so that the Frobenius norm squared $|A|_F^2$ is $Theta(n)$, the spectral norm squared $|A|_2^2=1$. Is it true that $sum_{i=1}^nmax_{1leq jleq n} |A_{ij}|^2$ is $Omega(n)$? Assume that $n$ is sufficiently large.



I cannot find a relation between matrix norms that can show this. The idea behind this question is that there are many singular values of $A$ that are $Theta(1)$.



Thanks!






linear-algebra matrices norms







share|cite|improve this question









New contributor




horxio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$








  • 2




    $begingroup$
    According to Wikipedia, $|A|_F=|A|_2$. Please, explain your notation!
    $endgroup$
    – W-t-P
    2 days ago






  • 1




    $begingroup$
    Frobenius norm, where did you find that? It is wrong what you are saying.
    $endgroup$
    – horxio
    2 days ago








  • 1




    $begingroup$
    What you are saying is incorrect. Can you please tell me where exactly you found this relation? It is wrong that the Frobenius norm is equal to the spectral norm. Think about it, if they were equal, why should we have two definitions? it holds that $||A||_F geq ||A||_2$.
    $endgroup$
    – horxio
    2 days ago






  • 2




    $begingroup$
    The last sentence in the ""Entrywise" matrix norms" reads: The special case p = 2 is the Frobenius norm; see also the "Frobenius norm" section below. Instead of arguing who is (in)correct, please explain your notation.
    $endgroup$
    – W-t-P
    2 days ago








  • 3




    $begingroup$
    @W-t-P I find your comments towards a new user a bit aggressive. The problem here is that $|A|_2$ is standard notation for two different things, as the Wikipedia page that you linked also notes (if you read a bit earlier, These norms again share the notation with the induced and entrywise p-norms, but they are different, and earlier the definition of the spectral norm). On the other hand, the terms Frobenius norm and spectral norm are unambiguous and look perfectly fine to me as explanations of the notation in OP's question.
    $endgroup$
    – Federico Poloni
    2 days ago
















4












$begingroup$


Let $A$ be a $n times n$ matrix so that the Frobenius norm squared $|A|_F^2$ is $Theta(n)$, the spectral norm squared $|A|_2^2=1$. Is it true that $sum_{i=1}^nmax_{1leq jleq n} |A_{ij}|^2$ is $Omega(n)$? Assume that $n$ is sufficiently large.



I cannot find a relation between matrix norms that can show this. The idea behind this question is that there are many singular values of $A$ that are $Theta(1)$.



Thanks!






linear-algebra matrices norms







share|cite|improve this question









New contributor




horxio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$








  • 2




    $begingroup$
    According to Wikipedia, $|A|_F=|A|_2$. Please, explain your notation!
    $endgroup$
    – W-t-P
    2 days ago






  • 1




    $begingroup$
    Frobenius norm, where did you find that? It is wrong what you are saying.
    $endgroup$
    – horxio
    2 days ago








  • 1




    $begingroup$
    What you are saying is incorrect. Can you please tell me where exactly you found this relation? It is wrong that the Frobenius norm is equal to the spectral norm. Think about it, if they were equal, why should we have two definitions? it holds that $||A||_F geq ||A||_2$.
    $endgroup$
    – horxio
    2 days ago






  • 2




    $begingroup$
    The last sentence in the ""Entrywise" matrix norms" reads: The special case p = 2 is the Frobenius norm; see also the "Frobenius norm" section below. Instead of arguing who is (in)correct, please explain your notation.
    $endgroup$
    – W-t-P
    2 days ago








  • 3




    $begingroup$
    @W-t-P I find your comments towards a new user a bit aggressive. The problem here is that $|A|_2$ is standard notation for two different things, as the Wikipedia page that you linked also notes (if you read a bit earlier, These norms again share the notation with the induced and entrywise p-norms, but they are different, and earlier the definition of the spectral norm). On the other hand, the terms Frobenius norm and spectral norm are unambiguous and look perfectly fine to me as explanations of the notation in OP's question.
    $endgroup$
    – Federico Poloni
    2 days ago














4












4








4





$begingroup$


Let $A$ be a $n times n$ matrix so that the Frobenius norm squared $|A|_F^2$ is $Theta(n)$, the spectral norm squared $|A|_2^2=1$. Is it true that $sum_{i=1}^nmax_{1leq jleq n} |A_{ij}|^2$ is $Omega(n)$? Assume that $n$ is sufficiently large.



I cannot find a relation between matrix norms that can show this. The idea behind this question is that there are many singular values of $A$ that are $Theta(1)$.



Thanks!






linear-algebra matrices norms







share|cite|improve this question









New contributor




horxio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$




Let $A$ be a $n times n$ matrix so that the Frobenius norm squared $|A|_F^2$ is $Theta(n)$, the spectral norm squared $|A|_2^2=1$. Is it true that $sum_{i=1}^nmax_{1leq jleq n} |A_{ij}|^2$ is $Omega(n)$? Assume that $n$ is sufficiently large.



I cannot find a relation between matrix norms that can show this. The idea behind this question is that there are many singular values of $A$ that are $Theta(1)$.



Thanks!






linear-algebra matrices norms




linear-algebra matrices norms






share|cite|improve this question









New contributor




horxio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|cite|improve this question









New contributor




horxio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|cite|improve this question




share|cite|improve this question








edited 2 days ago









Liviu Nicolaescu

25.9k260111




25.9k260111






New contributor




horxio 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









horxiohorxio

333




333




New contributor




horxio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





horxio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






horxio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.








  • 2




    $begingroup$
    According to Wikipedia, $|A|_F=|A|_2$. Please, explain your notation!
    $endgroup$
    – W-t-P
    2 days ago






  • 1




    $begingroup$
    Frobenius norm, where did you find that? It is wrong what you are saying.
    $endgroup$
    – horxio
    2 days ago








  • 1




    $begingroup$
    What you are saying is incorrect. Can you please tell me where exactly you found this relation? It is wrong that the Frobenius norm is equal to the spectral norm. Think about it, if they were equal, why should we have two definitions? it holds that $||A||_F geq ||A||_2$.
    $endgroup$
    – horxio
    2 days ago






  • 2




    $begingroup$
    The last sentence in the ""Entrywise" matrix norms" reads: The special case p = 2 is the Frobenius norm; see also the "Frobenius norm" section below. Instead of arguing who is (in)correct, please explain your notation.
    $endgroup$
    – W-t-P
    2 days ago








  • 3




    $begingroup$
    @W-t-P I find your comments towards a new user a bit aggressive. The problem here is that $|A|_2$ is standard notation for two different things, as the Wikipedia page that you linked also notes (if you read a bit earlier, These norms again share the notation with the induced and entrywise p-norms, but they are different, and earlier the definition of the spectral norm). On the other hand, the terms Frobenius norm and spectral norm are unambiguous and look perfectly fine to me as explanations of the notation in OP's question.
    $endgroup$
    – Federico Poloni
    2 days ago














  • 2




    $begingroup$
    According to Wikipedia, $|A|_F=|A|_2$. Please, explain your notation!
    $endgroup$
    – W-t-P
    2 days ago






  • 1




    $begingroup$
    Frobenius norm, where did you find that? It is wrong what you are saying.
    $endgroup$
    – horxio
    2 days ago








  • 1




    $begingroup$
    What you are saying is incorrect. Can you please tell me where exactly you found this relation? It is wrong that the Frobenius norm is equal to the spectral norm. Think about it, if they were equal, why should we have two definitions? it holds that $||A||_F geq ||A||_2$.
    $endgroup$
    – horxio
    2 days ago






  • 2




    $begingroup$
    The last sentence in the ""Entrywise" matrix norms" reads: The special case p = 2 is the Frobenius norm; see also the "Frobenius norm" section below. Instead of arguing who is (in)correct, please explain your notation.
    $endgroup$
    – W-t-P
    2 days ago








  • 3




    $begingroup$
    @W-t-P I find your comments towards a new user a bit aggressive. The problem here is that $|A|_2$ is standard notation for two different things, as the Wikipedia page that you linked also notes (if you read a bit earlier, These norms again share the notation with the induced and entrywise p-norms, but they are different, and earlier the definition of the spectral norm). On the other hand, the terms Frobenius norm and spectral norm are unambiguous and look perfectly fine to me as explanations of the notation in OP's question.
    $endgroup$
    – Federico Poloni
    2 days ago








2




2




$begingroup$
According to Wikipedia, $|A|_F=|A|_2$. Please, explain your notation!
$endgroup$
– W-t-P
2 days ago




$begingroup$
According to Wikipedia, $|A|_F=|A|_2$. Please, explain your notation!
$endgroup$
– W-t-P
2 days ago




1




1




$begingroup$
Frobenius norm, where did you find that? It is wrong what you are saying.
$endgroup$
– horxio
2 days ago






$begingroup$
Frobenius norm, where did you find that? It is wrong what you are saying.
$endgroup$
– horxio
2 days ago






1




1




$begingroup$
What you are saying is incorrect. Can you please tell me where exactly you found this relation? It is wrong that the Frobenius norm is equal to the spectral norm. Think about it, if they were equal, why should we have two definitions? it holds that $||A||_F geq ||A||_2$.
$endgroup$
– horxio
2 days ago




$begingroup$
What you are saying is incorrect. Can you please tell me where exactly you found this relation? It is wrong that the Frobenius norm is equal to the spectral norm. Think about it, if they were equal, why should we have two definitions? it holds that $||A||_F geq ||A||_2$.
$endgroup$
– horxio
2 days ago




2




2




$begingroup$
The last sentence in the ""Entrywise" matrix norms" reads: The special case p = 2 is the Frobenius norm; see also the "Frobenius norm" section below. Instead of arguing who is (in)correct, please explain your notation.
$endgroup$
– W-t-P
2 days ago






$begingroup$
The last sentence in the ""Entrywise" matrix norms" reads: The special case p = 2 is the Frobenius norm; see also the "Frobenius norm" section below. Instead of arguing who is (in)correct, please explain your notation.
$endgroup$
– W-t-P
2 days ago






3




3




$begingroup$
@W-t-P I find your comments towards a new user a bit aggressive. The problem here is that $|A|_2$ is standard notation for two different things, as the Wikipedia page that you linked also notes (if you read a bit earlier, These norms again share the notation with the induced and entrywise p-norms, but they are different, and earlier the definition of the spectral norm). On the other hand, the terms Frobenius norm and spectral norm are unambiguous and look perfectly fine to me as explanations of the notation in OP's question.
$endgroup$
– Federico Poloni
2 days ago




$begingroup$
@W-t-P I find your comments towards a new user a bit aggressive. The problem here is that $|A|_2$ is standard notation for two different things, as the Wikipedia page that you linked also notes (if you read a bit earlier, These norms again share the notation with the induced and entrywise p-norms, but they are different, and earlier the definition of the spectral norm). On the other hand, the terms Frobenius norm and spectral norm are unambiguous and look perfectly fine to me as explanations of the notation in OP's question.
$endgroup$
– Federico Poloni
2 days ago










1 Answer
1






active

oldest

votes


















4












$begingroup$

This is false in general, but true for matrices with non-negative entries.



For a counterexample, suppose that $n=p$ is prime, and consider the matrix
$$ A=left|p^{-1/2}left(frac{i-j}pright)right|_{i,j=0,dotsc,p-1} $$
where $(cdot/p)$ is the Legendre symbol. This is a circulant matrix; its non-zero eigenvalues are normalized Gaussian sums, equal $1$ in absolute value; hence, $|A|_2le 1$. Also, we have $|A|_F^2=p-1$. On the other hand,
$$ sum_i max_j |A_{ij}|^2 = 1. $$



Suppose now that all elements of $A$ are non-negative. Let $u_iin{mathbb R}^n$ be the row vectors of $A$, and denote by $|cdot|_p$ the $ell^p$-norm over ${mathbb R}^n$; when $p=2$, this is the standard Euclidean norm. The Frobenius norm of $A$ is $|A|_F^2=sum_i|u_i|_2^2$. Assuming that $|A|_F^2ge cn$ and $|A|_2^2le C$, we show that $sum_i|u_i|_infty^2ge C^{-1}c^2n$.



Denoting by $vec 1$ the all-$1$ vector, we have
$$ C ge |A|_2^2 = max_x frac{|Ax|_2^2}{|x|_2^2} ge frac{|Avec 1|_2^2}{|vec 1|_2^2} = frac1nsum_i |u_i|_1^2. $$
(It is this computation that uses the non-negativeness assumption.) This
implies
$$ sum_i |u_i|_1^2 le Cn $$
and, consequently, by Cauchy-Schwartz,
$$ cn le |A|_F^2 = sum_i |u_i|_2^2 le sum_i |u_i|_infty |u_i|_1 le left( sum_i |u_i|_infty^2right)^{1/2} left( sum_i |u_i|_1^2right)^{1/2} le
left( Cnsum_i |u_i|_infty^2right)^{1/2}, $$
which yields the desired estimate
$$ sum_i |u_i|_infty^2 ge C^{-1}c^2n. $$






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Hi Seva, basically the example you provided is wrong since $||A||_2 geq sqrt{n}gg 1$. Your example is about the spectral radius but not the spectral norm.
    $endgroup$
    – horxio
    2 days ago












  • $begingroup$
    I meant $||A||_2^2$ is $Omega(sqrt{n})$.
    $endgroup$
    – horxio
    2 days ago












  • $begingroup$
    (This answer has been completely changed, it should be correct now.)
    $endgroup$
    – Seva
    13 hours ago












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: "504"
};
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
});


}
});






horxio is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f327382%2frelation-between-frobenius-spectral-norm-and-sum-of-maxima%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









4












$begingroup$

This is false in general, but true for matrices with non-negative entries.



For a counterexample, suppose that $n=p$ is prime, and consider the matrix
$$ A=left|p^{-1/2}left(frac{i-j}pright)right|_{i,j=0,dotsc,p-1} $$
where $(cdot/p)$ is the Legendre symbol. This is a circulant matrix; its non-zero eigenvalues are normalized Gaussian sums, equal $1$ in absolute value; hence, $|A|_2le 1$. Also, we have $|A|_F^2=p-1$. On the other hand,
$$ sum_i max_j |A_{ij}|^2 = 1. $$



Suppose now that all elements of $A$ are non-negative. Let $u_iin{mathbb R}^n$ be the row vectors of $A$, and denote by $|cdot|_p$ the $ell^p$-norm over ${mathbb R}^n$; when $p=2$, this is the standard Euclidean norm. The Frobenius norm of $A$ is $|A|_F^2=sum_i|u_i|_2^2$. Assuming that $|A|_F^2ge cn$ and $|A|_2^2le C$, we show that $sum_i|u_i|_infty^2ge C^{-1}c^2n$.



Denoting by $vec 1$ the all-$1$ vector, we have
$$ C ge |A|_2^2 = max_x frac{|Ax|_2^2}{|x|_2^2} ge frac{|Avec 1|_2^2}{|vec 1|_2^2} = frac1nsum_i |u_i|_1^2. $$
(It is this computation that uses the non-negativeness assumption.) This
implies
$$ sum_i |u_i|_1^2 le Cn $$
and, consequently, by Cauchy-Schwartz,
$$ cn le |A|_F^2 = sum_i |u_i|_2^2 le sum_i |u_i|_infty |u_i|_1 le left( sum_i |u_i|_infty^2right)^{1/2} left( sum_i |u_i|_1^2right)^{1/2} le
left( Cnsum_i |u_i|_infty^2right)^{1/2}, $$
which yields the desired estimate
$$ sum_i |u_i|_infty^2 ge C^{-1}c^2n. $$






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Hi Seva, basically the example you provided is wrong since $||A||_2 geq sqrt{n}gg 1$. Your example is about the spectral radius but not the spectral norm.
    $endgroup$
    – horxio
    2 days ago












  • $begingroup$
    I meant $||A||_2^2$ is $Omega(sqrt{n})$.
    $endgroup$
    – horxio
    2 days ago












  • $begingroup$
    (This answer has been completely changed, it should be correct now.)
    $endgroup$
    – Seva
    13 hours ago
















4












$begingroup$

This is false in general, but true for matrices with non-negative entries.



For a counterexample, suppose that $n=p$ is prime, and consider the matrix
$$ A=left|p^{-1/2}left(frac{i-j}pright)right|_{i,j=0,dotsc,p-1} $$
where $(cdot/p)$ is the Legendre symbol. This is a circulant matrix; its non-zero eigenvalues are normalized Gaussian sums, equal $1$ in absolute value; hence, $|A|_2le 1$. Also, we have $|A|_F^2=p-1$. On the other hand,
$$ sum_i max_j |A_{ij}|^2 = 1. $$



Suppose now that all elements of $A$ are non-negative. Let $u_iin{mathbb R}^n$ be the row vectors of $A$, and denote by $|cdot|_p$ the $ell^p$-norm over ${mathbb R}^n$; when $p=2$, this is the standard Euclidean norm. The Frobenius norm of $A$ is $|A|_F^2=sum_i|u_i|_2^2$. Assuming that $|A|_F^2ge cn$ and $|A|_2^2le C$, we show that $sum_i|u_i|_infty^2ge C^{-1}c^2n$.



Denoting by $vec 1$ the all-$1$ vector, we have
$$ C ge |A|_2^2 = max_x frac{|Ax|_2^2}{|x|_2^2} ge frac{|Avec 1|_2^2}{|vec 1|_2^2} = frac1nsum_i |u_i|_1^2. $$
(It is this computation that uses the non-negativeness assumption.) This
implies
$$ sum_i |u_i|_1^2 le Cn $$
and, consequently, by Cauchy-Schwartz,
$$ cn le |A|_F^2 = sum_i |u_i|_2^2 le sum_i |u_i|_infty |u_i|_1 le left( sum_i |u_i|_infty^2right)^{1/2} left( sum_i |u_i|_1^2right)^{1/2} le
left( Cnsum_i |u_i|_infty^2right)^{1/2}, $$
which yields the desired estimate
$$ sum_i |u_i|_infty^2 ge C^{-1}c^2n. $$






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Hi Seva, basically the example you provided is wrong since $||A||_2 geq sqrt{n}gg 1$. Your example is about the spectral radius but not the spectral norm.
    $endgroup$
    – horxio
    2 days ago












  • $begingroup$
    I meant $||A||_2^2$ is $Omega(sqrt{n})$.
    $endgroup$
    – horxio
    2 days ago












  • $begingroup$
    (This answer has been completely changed, it should be correct now.)
    $endgroup$
    – Seva
    13 hours ago














4












4








4





$begingroup$

This is false in general, but true for matrices with non-negative entries.



For a counterexample, suppose that $n=p$ is prime, and consider the matrix
$$ A=left|p^{-1/2}left(frac{i-j}pright)right|_{i,j=0,dotsc,p-1} $$
where $(cdot/p)$ is the Legendre symbol. This is a circulant matrix; its non-zero eigenvalues are normalized Gaussian sums, equal $1$ in absolute value; hence, $|A|_2le 1$. Also, we have $|A|_F^2=p-1$. On the other hand,
$$ sum_i max_j |A_{ij}|^2 = 1. $$



Suppose now that all elements of $A$ are non-negative. Let $u_iin{mathbb R}^n$ be the row vectors of $A$, and denote by $|cdot|_p$ the $ell^p$-norm over ${mathbb R}^n$; when $p=2$, this is the standard Euclidean norm. The Frobenius norm of $A$ is $|A|_F^2=sum_i|u_i|_2^2$. Assuming that $|A|_F^2ge cn$ and $|A|_2^2le C$, we show that $sum_i|u_i|_infty^2ge C^{-1}c^2n$.



Denoting by $vec 1$ the all-$1$ vector, we have
$$ C ge |A|_2^2 = max_x frac{|Ax|_2^2}{|x|_2^2} ge frac{|Avec 1|_2^2}{|vec 1|_2^2} = frac1nsum_i |u_i|_1^2. $$
(It is this computation that uses the non-negativeness assumption.) This
implies
$$ sum_i |u_i|_1^2 le Cn $$
and, consequently, by Cauchy-Schwartz,
$$ cn le |A|_F^2 = sum_i |u_i|_2^2 le sum_i |u_i|_infty |u_i|_1 le left( sum_i |u_i|_infty^2right)^{1/2} left( sum_i |u_i|_1^2right)^{1/2} le
left( Cnsum_i |u_i|_infty^2right)^{1/2}, $$
which yields the desired estimate
$$ sum_i |u_i|_infty^2 ge C^{-1}c^2n. $$






share|cite|improve this answer











$endgroup$



This is false in general, but true for matrices with non-negative entries.



For a counterexample, suppose that $n=p$ is prime, and consider the matrix
$$ A=left|p^{-1/2}left(frac{i-j}pright)right|_{i,j=0,dotsc,p-1} $$
where $(cdot/p)$ is the Legendre symbol. This is a circulant matrix; its non-zero eigenvalues are normalized Gaussian sums, equal $1$ in absolute value; hence, $|A|_2le 1$. Also, we have $|A|_F^2=p-1$. On the other hand,
$$ sum_i max_j |A_{ij}|^2 = 1. $$



Suppose now that all elements of $A$ are non-negative. Let $u_iin{mathbb R}^n$ be the row vectors of $A$, and denote by $|cdot|_p$ the $ell^p$-norm over ${mathbb R}^n$; when $p=2$, this is the standard Euclidean norm. The Frobenius norm of $A$ is $|A|_F^2=sum_i|u_i|_2^2$. Assuming that $|A|_F^2ge cn$ and $|A|_2^2le C$, we show that $sum_i|u_i|_infty^2ge C^{-1}c^2n$.



Denoting by $vec 1$ the all-$1$ vector, we have
$$ C ge |A|_2^2 = max_x frac{|Ax|_2^2}{|x|_2^2} ge frac{|Avec 1|_2^2}{|vec 1|_2^2} = frac1nsum_i |u_i|_1^2. $$
(It is this computation that uses the non-negativeness assumption.) This
implies
$$ sum_i |u_i|_1^2 le Cn $$
and, consequently, by Cauchy-Schwartz,
$$ cn le |A|_F^2 = sum_i |u_i|_2^2 le sum_i |u_i|_infty |u_i|_1 le left( sum_i |u_i|_infty^2right)^{1/2} left( sum_i |u_i|_1^2right)^{1/2} le
left( Cnsum_i |u_i|_infty^2right)^{1/2}, $$
which yields the desired estimate
$$ sum_i |u_i|_infty^2 ge C^{-1}c^2n. $$







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited 13 hours ago

























answered 2 days ago









SevaSeva

12.8k138103




12.8k138103












  • $begingroup$
    Hi Seva, basically the example you provided is wrong since $||A||_2 geq sqrt{n}gg 1$. Your example is about the spectral radius but not the spectral norm.
    $endgroup$
    – horxio
    2 days ago












  • $begingroup$
    I meant $||A||_2^2$ is $Omega(sqrt{n})$.
    $endgroup$
    – horxio
    2 days ago












  • $begingroup$
    (This answer has been completely changed, it should be correct now.)
    $endgroup$
    – Seva
    13 hours ago


















  • $begingroup$
    Hi Seva, basically the example you provided is wrong since $||A||_2 geq sqrt{n}gg 1$. Your example is about the spectral radius but not the spectral norm.
    $endgroup$
    – horxio
    2 days ago












  • $begingroup$
    I meant $||A||_2^2$ is $Omega(sqrt{n})$.
    $endgroup$
    – horxio
    2 days ago












  • $begingroup$
    (This answer has been completely changed, it should be correct now.)
    $endgroup$
    – Seva
    13 hours ago
















$begingroup$
Hi Seva, basically the example you provided is wrong since $||A||_2 geq sqrt{n}gg 1$. Your example is about the spectral radius but not the spectral norm.
$endgroup$
– horxio
2 days ago






$begingroup$
Hi Seva, basically the example you provided is wrong since $||A||_2 geq sqrt{n}gg 1$. Your example is about the spectral radius but not the spectral norm.
$endgroup$
– horxio
2 days ago














$begingroup$
I meant $||A||_2^2$ is $Omega(sqrt{n})$.
$endgroup$
– horxio
2 days ago






$begingroup$
I meant $||A||_2^2$ is $Omega(sqrt{n})$.
$endgroup$
– horxio
2 days ago














$begingroup$
(This answer has been completely changed, it should be correct now.)
$endgroup$
– Seva
13 hours ago




$begingroup$
(This answer has been completely changed, it should be correct now.)
$endgroup$
– Seva
13 hours ago










horxio is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















horxio is a new contributor. Be nice, and check out our Code of Conduct.













horxio is a new contributor. Be nice, and check out our Code of Conduct.












horxio is a new contributor. Be nice, and check out our Code of Conduct.
















Thanks for contributing an answer to MathOverflow!


  • 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.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f327382%2frelation-between-frobenius-spectral-norm-and-sum-of-maxima%23new-answer', 'question_page');
}
);

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







-

Popular posts from this blog

What other Star Trek series did the main TNG cast show up in?

Image
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0; } 4 I'm referring to Picard, Riker, Data, Worf, Geordi, Dr. Crusher, Wesley Crusher, Chief O'Brien and family, Deanna Troi, Guinan. I know Picard and Worf show up on DS9, though I haven't seen it myself. I'm curious what happened to the characters after that last episode of TNG? star-trek star-trek-tng share | improve this question edited 10 hours ago Ham Sandwich 6,051 2 25 75 ...
Read more

Berlina muro

Image
La berlina muro ĉe Bethaniendamm, 1986 La berlina muro aŭ simple la muro [1] , nomita ankaŭ "kontraŭfaŝisma remparo" en propaganda lingvo de la iama Germana Demokratia Respubliko, estis parto de la interngermana limo, kiu dividis de la 13-a de aŭgusto 1961 ĝis la 9-a de novembro 1989 okcidentan Berlinon de la orienta parto de la urbo kaj de la ĉirkaŭa tereno de la GDR. Ĝi estis unu el la plej famaj simboloj de la malvarma milito kaj de la disdivido de Germanio. Pli ol simpla muro, la berlina muro estis fakte tuta defendokonstruaĵo kun du muroj, ena malplena strio, rondirvojo, gardturoj kaj alarmsistemoj. Dum la provo transiri la severe garditan limon al okcidenta Berlino multaj homoj estis mortigitaj. La preciza nombro de viktimoj estas pridisputita kaj ne certa; la nombroj anoncataj varias inter 86 kaj 238 mortintoj. La malplifortiĝo de Sovetunio kaj la politiko de liberigo gvidita de Miĥail Gorbaĉov ebligis al la orientgermanoj faligi la 9-an de novembro 1989 l...
Read more

Berlina aerponto

Image
Flugkoridoroj dum la blokado de Berlino La Berlina aerponto estas la provizigo de okcidenta Berlino per aviadiloj fare de la aliancanoj inter la 23-a de junio 1948 kaj la 12-a de majo 1949 dum la blokado de Berlino fare de la sovetia armeo. Enhavo 1 Historio 1.1 La aerkoridoroj 1.2 Unuaj flugoj 1.3 Plibonigo de la aerponto 1.4 Fino de la aerponto 1.5 Rozinbombiloj 1.6 Bilanco 2 Flughavenoj 2.1 Berlino 2.2 Okcidenta Germanio 3 Aviadiloj de la berlina aerponto 4 15-a datreveno de la aerponto 5 Bibliografio 6 Referencoj 7 Eksteraj ligiloj Historio | General Lucius D. Clay, militguberniestro de la usona okupadzono Jam antaŭ la berlina aerponto estiĝis la malgranda aerponto . La estro de la sovetia militadministracio en Germanio, Vasili Daniloviĉ Sokolovski, ordonis la 1-an de aprilo 1948, kiel reago al la konferenco de Londono inter britoj, francoj kaj reprezentantoj de Benelukso pri aligo de Germa...
Read more