Find $min(operatorname{trace}(AA^T))$ for invertible $A_{ntimes n}$












3












$begingroup$


For invertible $A_{ntimes n}$ find $min(operatorname{trace}(AA^T))$



(a) $0$

(b) $1$

(c) $n$

(d) $n^2$



Clearly for $A=I$, it is $n$, and I am unable to get any lower values, but how do I prove it.










share|cite|improve this question











$endgroup$








  • 2




    $begingroup$
    Well if you take $varepsiloncdot I_n$ for small $varepsilon$ then you get a lower value, to begin with.
    $endgroup$
    – Ian Coley
    May 12 '14 at 2:32








  • 1




    $begingroup$
    and in that way you get all positive values for the function. Since it only takes positive values, this gives you the answer.
    $endgroup$
    – Mariano Suárez-Álvarez
    May 12 '14 at 2:33










  • $begingroup$
    If $A$ is real, there is no minimum value. As Mariano mentioned, if you compute the $i$th diagonal entry of $AA^{T}$, this is the norm squared of the $i$th row of $A$ and is hence positive. Thus, the trace is positive. But Ian's answer shows that you can make the trace as close to 0 as you like.
    $endgroup$
    – Siddharth Venkatesh
    May 12 '14 at 2:35






  • 1




    $begingroup$
    If the entries must be integers, $n$ is correct.
    $endgroup$
    – Will Jagy
    May 12 '14 at 2:36










  • $begingroup$
    Well thanks to all of you. This is a multiple choice question with options $0$,$1$, $n$ and $n^2$. But clearly $0$ cant be attained, but $0^+$ can be. I guess the question was set keeping integers in mind. @WillJagy But how do I prove it formally (for integral values)? I mean why cant I have $n-1$ or less?
    $endgroup$
    – Morty
    May 12 '14 at 2:47


















3












$begingroup$


For invertible $A_{ntimes n}$ find $min(operatorname{trace}(AA^T))$



(a) $0$

(b) $1$

(c) $n$

(d) $n^2$



Clearly for $A=I$, it is $n$, and I am unable to get any lower values, but how do I prove it.










share|cite|improve this question











$endgroup$








  • 2




    $begingroup$
    Well if you take $varepsiloncdot I_n$ for small $varepsilon$ then you get a lower value, to begin with.
    $endgroup$
    – Ian Coley
    May 12 '14 at 2:32








  • 1




    $begingroup$
    and in that way you get all positive values for the function. Since it only takes positive values, this gives you the answer.
    $endgroup$
    – Mariano Suárez-Álvarez
    May 12 '14 at 2:33










  • $begingroup$
    If $A$ is real, there is no minimum value. As Mariano mentioned, if you compute the $i$th diagonal entry of $AA^{T}$, this is the norm squared of the $i$th row of $A$ and is hence positive. Thus, the trace is positive. But Ian's answer shows that you can make the trace as close to 0 as you like.
    $endgroup$
    – Siddharth Venkatesh
    May 12 '14 at 2:35






  • 1




    $begingroup$
    If the entries must be integers, $n$ is correct.
    $endgroup$
    – Will Jagy
    May 12 '14 at 2:36










  • $begingroup$
    Well thanks to all of you. This is a multiple choice question with options $0$,$1$, $n$ and $n^2$. But clearly $0$ cant be attained, but $0^+$ can be. I guess the question was set keeping integers in mind. @WillJagy But how do I prove it formally (for integral values)? I mean why cant I have $n-1$ or less?
    $endgroup$
    – Morty
    May 12 '14 at 2:47
















3












3








3


5



$begingroup$


For invertible $A_{ntimes n}$ find $min(operatorname{trace}(AA^T))$



(a) $0$

(b) $1$

(c) $n$

(d) $n^2$



Clearly for $A=I$, it is $n$, and I am unable to get any lower values, but how do I prove it.










share|cite|improve this question











$endgroup$




For invertible $A_{ntimes n}$ find $min(operatorname{trace}(AA^T))$



(a) $0$

(b) $1$

(c) $n$

(d) $n^2$



Clearly for $A=I$, it is $n$, and I am unable to get any lower values, but how do I prove it.







linear-algebra matrices trace






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 1 at 8:20









user26857

39.4k124183




39.4k124183










asked May 12 '14 at 2:30









MortyMorty

337111




337111








  • 2




    $begingroup$
    Well if you take $varepsiloncdot I_n$ for small $varepsilon$ then you get a lower value, to begin with.
    $endgroup$
    – Ian Coley
    May 12 '14 at 2:32








  • 1




    $begingroup$
    and in that way you get all positive values for the function. Since it only takes positive values, this gives you the answer.
    $endgroup$
    – Mariano Suárez-Álvarez
    May 12 '14 at 2:33










  • $begingroup$
    If $A$ is real, there is no minimum value. As Mariano mentioned, if you compute the $i$th diagonal entry of $AA^{T}$, this is the norm squared of the $i$th row of $A$ and is hence positive. Thus, the trace is positive. But Ian's answer shows that you can make the trace as close to 0 as you like.
    $endgroup$
    – Siddharth Venkatesh
    May 12 '14 at 2:35






  • 1




    $begingroup$
    If the entries must be integers, $n$ is correct.
    $endgroup$
    – Will Jagy
    May 12 '14 at 2:36










  • $begingroup$
    Well thanks to all of you. This is a multiple choice question with options $0$,$1$, $n$ and $n^2$. But clearly $0$ cant be attained, but $0^+$ can be. I guess the question was set keeping integers in mind. @WillJagy But how do I prove it formally (for integral values)? I mean why cant I have $n-1$ or less?
    $endgroup$
    – Morty
    May 12 '14 at 2:47
















  • 2




    $begingroup$
    Well if you take $varepsiloncdot I_n$ for small $varepsilon$ then you get a lower value, to begin with.
    $endgroup$
    – Ian Coley
    May 12 '14 at 2:32








  • 1




    $begingroup$
    and in that way you get all positive values for the function. Since it only takes positive values, this gives you the answer.
    $endgroup$
    – Mariano Suárez-Álvarez
    May 12 '14 at 2:33










  • $begingroup$
    If $A$ is real, there is no minimum value. As Mariano mentioned, if you compute the $i$th diagonal entry of $AA^{T}$, this is the norm squared of the $i$th row of $A$ and is hence positive. Thus, the trace is positive. But Ian's answer shows that you can make the trace as close to 0 as you like.
    $endgroup$
    – Siddharth Venkatesh
    May 12 '14 at 2:35






  • 1




    $begingroup$
    If the entries must be integers, $n$ is correct.
    $endgroup$
    – Will Jagy
    May 12 '14 at 2:36










  • $begingroup$
    Well thanks to all of you. This is a multiple choice question with options $0$,$1$, $n$ and $n^2$. But clearly $0$ cant be attained, but $0^+$ can be. I guess the question was set keeping integers in mind. @WillJagy But how do I prove it formally (for integral values)? I mean why cant I have $n-1$ or less?
    $endgroup$
    – Morty
    May 12 '14 at 2:47










2




2




$begingroup$
Well if you take $varepsiloncdot I_n$ for small $varepsilon$ then you get a lower value, to begin with.
$endgroup$
– Ian Coley
May 12 '14 at 2:32






$begingroup$
Well if you take $varepsiloncdot I_n$ for small $varepsilon$ then you get a lower value, to begin with.
$endgroup$
– Ian Coley
May 12 '14 at 2:32






1




1




$begingroup$
and in that way you get all positive values for the function. Since it only takes positive values, this gives you the answer.
$endgroup$
– Mariano Suárez-Álvarez
May 12 '14 at 2:33




$begingroup$
and in that way you get all positive values for the function. Since it only takes positive values, this gives you the answer.
$endgroup$
– Mariano Suárez-Álvarez
May 12 '14 at 2:33












$begingroup$
If $A$ is real, there is no minimum value. As Mariano mentioned, if you compute the $i$th diagonal entry of $AA^{T}$, this is the norm squared of the $i$th row of $A$ and is hence positive. Thus, the trace is positive. But Ian's answer shows that you can make the trace as close to 0 as you like.
$endgroup$
– Siddharth Venkatesh
May 12 '14 at 2:35




$begingroup$
If $A$ is real, there is no minimum value. As Mariano mentioned, if you compute the $i$th diagonal entry of $AA^{T}$, this is the norm squared of the $i$th row of $A$ and is hence positive. Thus, the trace is positive. But Ian's answer shows that you can make the trace as close to 0 as you like.
$endgroup$
– Siddharth Venkatesh
May 12 '14 at 2:35




1




1




$begingroup$
If the entries must be integers, $n$ is correct.
$endgroup$
– Will Jagy
May 12 '14 at 2:36




$begingroup$
If the entries must be integers, $n$ is correct.
$endgroup$
– Will Jagy
May 12 '14 at 2:36












$begingroup$
Well thanks to all of you. This is a multiple choice question with options $0$,$1$, $n$ and $n^2$. But clearly $0$ cant be attained, but $0^+$ can be. I guess the question was set keeping integers in mind. @WillJagy But how do I prove it formally (for integral values)? I mean why cant I have $n-1$ or less?
$endgroup$
– Morty
May 12 '14 at 2:47






$begingroup$
Well thanks to all of you. This is a multiple choice question with options $0$,$1$, $n$ and $n^2$. But clearly $0$ cant be attained, but $0^+$ can be. I guess the question was set keeping integers in mind. @WillJagy But how do I prove it formally (for integral values)? I mean why cant I have $n-1$ or less?
$endgroup$
– Morty
May 12 '14 at 2:47












1 Answer
1






active

oldest

votes


















7












$begingroup$

I will assume all the entries are integers. By multiplying out the matrices, you see that
$$ text{trace}(A^TA) = sum_{i,j} a_{i,j}^2 .$$
Suppose $text{trace}(A^TA) < n$. Then at most $n-1$ entries must be non-zero, meaning that at least one column of the matrix is all zeros. Hence $A$ is not invertible.



Hence $text{trace}(A^TA) ge n$. We know that the value $n$ can be obtained (e.g. by the identity, or any permutation matrix).






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Nice proof by the way. I recently discussed this question with my guide, it is a bit trickier than it seems. Since nothing is said about the entries in $A$, and the trace is the sum of inner products of $i$th row with itself (as Siddharth has pointed out), considering entries as integers, we get the answer to be $n$; considering entries are real, there doesn't exist any minimum (since we can get $epsilon$, $epsilon rightarrow 0$) and (here is the punch), considering complex entries, we can get $-infty$. So this question is better suited for a subjective answer than objective.
    $endgroup$
    – Morty
    May 12 '14 at 8:03












  • $begingroup$
    Anyhow among the options $0$ can also be achieved (with complex entries). So it comes down to what the question setter thought of while framing this :).
    $endgroup$
    – Morty
    May 12 '14 at 8:05












  • $begingroup$
    @Morty, in what possible way doe this question have a «subjective answer»?! That the minimum depends on the field is a quite objective fact.
    $endgroup$
    – Mariano Suárez-Álvarez
    May 14 '14 at 0:36










  • $begingroup$
    @MarianoSuarez-Alvarez I meant that you can check a box since the field is not clear, and the option for the most general field, i.e. complex, is missing.
    $endgroup$
    – Morty
    May 14 '14 at 4:55











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
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f791140%2ffind-min-operatornametraceaat-for-invertible-a-n-times-n%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









7












$begingroup$

I will assume all the entries are integers. By multiplying out the matrices, you see that
$$ text{trace}(A^TA) = sum_{i,j} a_{i,j}^2 .$$
Suppose $text{trace}(A^TA) < n$. Then at most $n-1$ entries must be non-zero, meaning that at least one column of the matrix is all zeros. Hence $A$ is not invertible.



Hence $text{trace}(A^TA) ge n$. We know that the value $n$ can be obtained (e.g. by the identity, or any permutation matrix).






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Nice proof by the way. I recently discussed this question with my guide, it is a bit trickier than it seems. Since nothing is said about the entries in $A$, and the trace is the sum of inner products of $i$th row with itself (as Siddharth has pointed out), considering entries as integers, we get the answer to be $n$; considering entries are real, there doesn't exist any minimum (since we can get $epsilon$, $epsilon rightarrow 0$) and (here is the punch), considering complex entries, we can get $-infty$. So this question is better suited for a subjective answer than objective.
    $endgroup$
    – Morty
    May 12 '14 at 8:03












  • $begingroup$
    Anyhow among the options $0$ can also be achieved (with complex entries). So it comes down to what the question setter thought of while framing this :).
    $endgroup$
    – Morty
    May 12 '14 at 8:05












  • $begingroup$
    @Morty, in what possible way doe this question have a «subjective answer»?! That the minimum depends on the field is a quite objective fact.
    $endgroup$
    – Mariano Suárez-Álvarez
    May 14 '14 at 0:36










  • $begingroup$
    @MarianoSuarez-Alvarez I meant that you can check a box since the field is not clear, and the option for the most general field, i.e. complex, is missing.
    $endgroup$
    – Morty
    May 14 '14 at 4:55
















7












$begingroup$

I will assume all the entries are integers. By multiplying out the matrices, you see that
$$ text{trace}(A^TA) = sum_{i,j} a_{i,j}^2 .$$
Suppose $text{trace}(A^TA) < n$. Then at most $n-1$ entries must be non-zero, meaning that at least one column of the matrix is all zeros. Hence $A$ is not invertible.



Hence $text{trace}(A^TA) ge n$. We know that the value $n$ can be obtained (e.g. by the identity, or any permutation matrix).






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Nice proof by the way. I recently discussed this question with my guide, it is a bit trickier than it seems. Since nothing is said about the entries in $A$, and the trace is the sum of inner products of $i$th row with itself (as Siddharth has pointed out), considering entries as integers, we get the answer to be $n$; considering entries are real, there doesn't exist any minimum (since we can get $epsilon$, $epsilon rightarrow 0$) and (here is the punch), considering complex entries, we can get $-infty$. So this question is better suited for a subjective answer than objective.
    $endgroup$
    – Morty
    May 12 '14 at 8:03












  • $begingroup$
    Anyhow among the options $0$ can also be achieved (with complex entries). So it comes down to what the question setter thought of while framing this :).
    $endgroup$
    – Morty
    May 12 '14 at 8:05












  • $begingroup$
    @Morty, in what possible way doe this question have a «subjective answer»?! That the minimum depends on the field is a quite objective fact.
    $endgroup$
    – Mariano Suárez-Álvarez
    May 14 '14 at 0:36










  • $begingroup$
    @MarianoSuarez-Alvarez I meant that you can check a box since the field is not clear, and the option for the most general field, i.e. complex, is missing.
    $endgroup$
    – Morty
    May 14 '14 at 4:55














7












7








7





$begingroup$

I will assume all the entries are integers. By multiplying out the matrices, you see that
$$ text{trace}(A^TA) = sum_{i,j} a_{i,j}^2 .$$
Suppose $text{trace}(A^TA) < n$. Then at most $n-1$ entries must be non-zero, meaning that at least one column of the matrix is all zeros. Hence $A$ is not invertible.



Hence $text{trace}(A^TA) ge n$. We know that the value $n$ can be obtained (e.g. by the identity, or any permutation matrix).






share|cite|improve this answer









$endgroup$



I will assume all the entries are integers. By multiplying out the matrices, you see that
$$ text{trace}(A^TA) = sum_{i,j} a_{i,j}^2 .$$
Suppose $text{trace}(A^TA) < n$. Then at most $n-1$ entries must be non-zero, meaning that at least one column of the matrix is all zeros. Hence $A$ is not invertible.



Hence $text{trace}(A^TA) ge n$. We know that the value $n$ can be obtained (e.g. by the identity, or any permutation matrix).







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered May 12 '14 at 3:28









Stephen Montgomery-SmithStephen Montgomery-Smith

17.8k12247




17.8k12247












  • $begingroup$
    Nice proof by the way. I recently discussed this question with my guide, it is a bit trickier than it seems. Since nothing is said about the entries in $A$, and the trace is the sum of inner products of $i$th row with itself (as Siddharth has pointed out), considering entries as integers, we get the answer to be $n$; considering entries are real, there doesn't exist any minimum (since we can get $epsilon$, $epsilon rightarrow 0$) and (here is the punch), considering complex entries, we can get $-infty$. So this question is better suited for a subjective answer than objective.
    $endgroup$
    – Morty
    May 12 '14 at 8:03












  • $begingroup$
    Anyhow among the options $0$ can also be achieved (with complex entries). So it comes down to what the question setter thought of while framing this :).
    $endgroup$
    – Morty
    May 12 '14 at 8:05












  • $begingroup$
    @Morty, in what possible way doe this question have a «subjective answer»?! That the minimum depends on the field is a quite objective fact.
    $endgroup$
    – Mariano Suárez-Álvarez
    May 14 '14 at 0:36










  • $begingroup$
    @MarianoSuarez-Alvarez I meant that you can check a box since the field is not clear, and the option for the most general field, i.e. complex, is missing.
    $endgroup$
    – Morty
    May 14 '14 at 4:55


















  • $begingroup$
    Nice proof by the way. I recently discussed this question with my guide, it is a bit trickier than it seems. Since nothing is said about the entries in $A$, and the trace is the sum of inner products of $i$th row with itself (as Siddharth has pointed out), considering entries as integers, we get the answer to be $n$; considering entries are real, there doesn't exist any minimum (since we can get $epsilon$, $epsilon rightarrow 0$) and (here is the punch), considering complex entries, we can get $-infty$. So this question is better suited for a subjective answer than objective.
    $endgroup$
    – Morty
    May 12 '14 at 8:03












  • $begingroup$
    Anyhow among the options $0$ can also be achieved (with complex entries). So it comes down to what the question setter thought of while framing this :).
    $endgroup$
    – Morty
    May 12 '14 at 8:05












  • $begingroup$
    @Morty, in what possible way doe this question have a «subjective answer»?! That the minimum depends on the field is a quite objective fact.
    $endgroup$
    – Mariano Suárez-Álvarez
    May 14 '14 at 0:36










  • $begingroup$
    @MarianoSuarez-Alvarez I meant that you can check a box since the field is not clear, and the option for the most general field, i.e. complex, is missing.
    $endgroup$
    – Morty
    May 14 '14 at 4:55
















$begingroup$
Nice proof by the way. I recently discussed this question with my guide, it is a bit trickier than it seems. Since nothing is said about the entries in $A$, and the trace is the sum of inner products of $i$th row with itself (as Siddharth has pointed out), considering entries as integers, we get the answer to be $n$; considering entries are real, there doesn't exist any minimum (since we can get $epsilon$, $epsilon rightarrow 0$) and (here is the punch), considering complex entries, we can get $-infty$. So this question is better suited for a subjective answer than objective.
$endgroup$
– Morty
May 12 '14 at 8:03






$begingroup$
Nice proof by the way. I recently discussed this question with my guide, it is a bit trickier than it seems. Since nothing is said about the entries in $A$, and the trace is the sum of inner products of $i$th row with itself (as Siddharth has pointed out), considering entries as integers, we get the answer to be $n$; considering entries are real, there doesn't exist any minimum (since we can get $epsilon$, $epsilon rightarrow 0$) and (here is the punch), considering complex entries, we can get $-infty$. So this question is better suited for a subjective answer than objective.
$endgroup$
– Morty
May 12 '14 at 8:03














$begingroup$
Anyhow among the options $0$ can also be achieved (with complex entries). So it comes down to what the question setter thought of while framing this :).
$endgroup$
– Morty
May 12 '14 at 8:05






$begingroup$
Anyhow among the options $0$ can also be achieved (with complex entries). So it comes down to what the question setter thought of while framing this :).
$endgroup$
– Morty
May 12 '14 at 8:05














$begingroup$
@Morty, in what possible way doe this question have a «subjective answer»?! That the minimum depends on the field is a quite objective fact.
$endgroup$
– Mariano Suárez-Álvarez
May 14 '14 at 0:36




$begingroup$
@Morty, in what possible way doe this question have a «subjective answer»?! That the minimum depends on the field is a quite objective fact.
$endgroup$
– Mariano Suárez-Álvarez
May 14 '14 at 0:36












$begingroup$
@MarianoSuarez-Alvarez I meant that you can check a box since the field is not clear, and the option for the most general field, i.e. complex, is missing.
$endgroup$
– Morty
May 14 '14 at 4:55




$begingroup$
@MarianoSuarez-Alvarez I meant that you can check a box since the field is not clear, and the option for the most general field, i.e. complex, is missing.
$endgroup$
– Morty
May 14 '14 at 4:55


















draft saved

draft discarded




















































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.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f791140%2ffind-min-operatornametraceaat-for-invertible-a-n-times-n%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

Probability when a professor distributes a quiz and homework assignment to a class of n students.

Aardman Animations

Are they similar matrix