4
$\begingroup$

Could I please get some help with the following true/sometimes true/false questions?

1) If $A$ is 3-by-4, then for every $\vec{z}$ $\in$ $\mathbb{R^{3}}$ there are infinitely many solutions $\vec{x}^{*}$ to $A^{T}A\vec{x}^{*}$=$A^{T}\vec{z}$

This is related to least-squares, I can see how it could be sometimes true, for example if A is the zero matrix. But I don't know how to provide a more general answer, can you explain the reasoning in this?

I am not sure if this is what I am looking for, but I think we said that $\mathbb{R^{n}}$ can always be decomposed into a subspace and its perp. So could I argue that since I am decomposing z, and its in $\mathbb{R^{n}}$, it will always be a combination of basis vectors of Im A and its perp?

2) $A$ is n-by-n and magnitude of $A\vec{u}$=1 for all unit vectors $\vec{u}$. $A$ is orthogonal.

Frin what is given to me I know that $A\vec{u}$ dot $A\vec{u}$=1 so $u^{T}A^{T}Au$=1. Not sure how to go from here.

3) If $S$ is 2-by-2 and invertible, and $T$: $\mathbb{R^{2x2}}\to\mathbb{R^{2x2}}$ is represented as $T(M)=S^{-1}MS$ then $T$ is an isomorphism.

We can prove that M=0 if T(M)=0 by taking $S^{-1}$ from the left of $SMS^{-1}$=0 and then $S$ from the right to get M=0. That's how any matrix N can be constructed from M, too => $M=S^{-1}NS$

4) A product of a matrix times its transpose is always symmetric.

Figured this one out -- always true.

2 Answers 2

2

So, (1) is at least "sometimes true", which you can establish by simply producing an example (which you have). The only question is whether it is always true.

Now, from studying least squares you probably saw that $\mathrm{rank}(A^TA) = \mathrm{rank}(A)$. Since $A$ is $3\times 4$ and $A^TA$ is $4\times 4$, then $A^TA$ is not invertible. That means that if you can find a solution to $A^TA\mathbf{x} = A^T\mathbf{z}$ for some specific $\mathbf{z}$, then that equation has infinitely many solutions (take any specific solution $\mathbf{s}$, and for every solution $\mathbf{n}$ to $A^TA\mathbf{x}=\mathbf{0}$, of which there are infinitely many because $A^TA$ is not invertible, you have that $\mathbf{s}+\mathbf{n}$ is a solution. So it really comes down to asking whether $A^TA\mathbf{x} = A^T\mathbf{z}$ always has at least one solution for all $\mathbf{z}$, or whether there is at least one $\mathbf{z}$ for which there are no solutions.

At this point, thinking about least squares, you should either figure out how to argue that there has to be at least one solution (and therefore infinitely many) for all $\mathbf{z}$; or else find an example where it does not have at least one solution. If you can find an example, then the example where it fails and the example where it works shows that it is "sometimes true"; if you can show it always has solutions, then you have your proof that it is "true."

Added. There are two parts to this argument as I sketched it: first you need to show that for every choice of $\vec{z}$, the system $A^TA\vec{x}=A^T\vec{z}$ has at least one solution. For that, what you know about least squares solutions should be useful, so you are on the right track when you realized that this is related to least squares.

Remember: if $\vec{z}$ is any vector, will $A\vec{x}=\vec{z}$ always have a least squares solutions (yes; you already explained why: it's just the vector in the range of $A$ that is closed to $\vec{z}$); and, will a least squares solution always be a solution to $A^TA\vec{x}=A^T\vec{z}$? (You probably proved or saw a theorem about this when you were figuring out how to do least squares; if so, you can just invoke that result).

After proving that for every $\vec{z}$ the system $A^TA\vec{x}=A^T\vec{z}$ always has at least one solution, you need to show that it always has infinitely many solutions. This is equivalent to asking whether $A^TA$ is invertible or not (you should explain why this is so; that is, that if it has more than one solution then $A^TA$ is not invertible, if $A^TA$ is not invertible, then it has more than one solution). Then explain why $A^TA$ cannot be invertible in this case.

(2) Again: you know that this is at least "sometimes true" (for example, $\mathbf{A}=\mathbf{I}$). The question is whether it is always true or not.

What characterizations of orthogonal matrices do you know? I assume it's that $A$ is orthogonal if and only if $A^TA = AA^T = I$?

Added. You are on the right track. You know that $A\vec{u}\cdot A\vec{u}=1$, and therefore that $\vec{u}\cdot(A^TA\vec{u}) = 1$ for all unit vectors $\vec{u}$, and therefore that $\vec{u} \cdot (\vec{u}-A^TA\vec{u}) = 0$ for all unit vectors $\vec{u}$. Now notice that $I - A^TA$ is symmetric; so you can find an orthonormal basis of eigenvectors of $I - A^TA$. If $\vec{u}$ is a unit eigenvector of $I-A^TA$, what does $\vec{u}\cdot(I- A^TA)\vec{u} = 0$ tell you?

(3): Again, you know this is at least "sometimes true". So, you need to determine: Is $T$ linear? Is $T$ one-to-one? Is it onto?

Linearity I'll leave to you. For one-to-one: suppose $T(M)=0$; does it follow that $M=0$? Start playing with $SMS^{-1}=0$ and see what you can conclude.

For surjectivity: given a matrix $N$, can you find an $M$ such that $T(M)=N$?

Added: You've solved (3); it's always true.

  • 0
    @Arturo: For the first one it seems to me that there will always be solutions, since we are essentially projecting onto the image of A, which can always be done. Am I correct in my reasoning, or am I omitting something? The least square solution is the vector that minimizes the distance between z and Ax, so it seems to me that there always has to be some kind of minimal distance, at least conceptually.2011-03-12
  • 0
    @Arturo: For the second part, I could say that since Au=1 for all unit vectors u, then magnitude Au=1, and that means that Au dot Au=1. This implies that $u^{T}A^{T}Au$=1. Am I on the right track?2011-03-12
  • 0
    @Arturo: For the third question, I think M has to equal to 0, otherwise a product of non-zero matrices would not result into a zero matrix (as far as I know). I am not sure about surjectivity -- if S is an identity matrix it obviously works, but I would think it should work with any other invertible n by n matrix too. Linearity (respecting scalar multiplication and addition) appears to work too, though I am not sure how to prove it rigorously.2011-03-12
  • 0
    @Jared: For the first part: *if* you know that there is always a least squares solutions, *and* you can show that a least squares solutions would necessarily be a solution to $A^TA\mathbf{x} = A^T\mathbf{z}$, then that's the argument you want to make (you may have proven these facts along the way when you developed least squares; if so, then invoke them. The argument would be: there is always a least squares solutions; and the solution gives at least one solution to $A^TA\mathbf{x} = A^T\mathbf{z}$; and having at least one solution guarantees infinitely many [by the argument given].)2011-03-12
  • 0
    @Jared: It is false that the product of nonzero matrices must be nonzero: square $$\left(\begin{array}{cc}0&1\\0&0\end{array}\right)$$for example. But here you know that $S$ is invertible. What happens if you take the equality $SMS^{-1}=0$ and multiply both sides by $S^{-1}$ on the left?2011-03-12
  • 0
    @Arturo: I am not sure if this is what I am looking for, but I think we said that $\mathbb{R^{n}}$ can always be decomposed into a subspace and its perp. So could I argue that since I am decomposing z, and its in $\mathbb{R^{n}}$, it will always be a combination of basis vectors of Im A and its perp?2011-03-12
  • 0
    @Jared: Comments are too constricted. I suggest you edit your question with your attempts; then I can edit my answer to address them.2011-03-12
  • 0
    @Arturo: Oh I see. We will get $MS^{-1}$=0 and then I can multiply by S from the right, and get M=0.2011-03-12
  • 0
    @Jared: Bingo. And now, given an $N$, can you come with an $M$ such that $SMS^{-1}=N$? Hint: Same idea...2011-03-12
  • 0
    @Arturo: I edited my question, thank you2011-03-12
  • 0
    @Arturo: Sorry I am confused, could you explain why Au dot Au is equal to zero? I thought it would be equal to one, since the magnitude of Au=1 for any unit vector as given in the problem2011-03-12
  • 0
    @Jared: Sorry; that's my fault. I wrote something wrong. I edited it. It was meant to be $(I-A^TA)\vec{u}$, not $A^TA\vec{u}$.2011-03-12
  • 0
    @Arturo: I think you still mean Au dot Au equals 1, not zero. I followed your argument up until the moment when you say "if u is an eigenvector of I-$A^{T}A$..." I don't see why it is such, sorry.2011-03-12
  • 0
    @Jared: Missed one in the edit sorry.... I'm not assuming the $\vec{u}$ I started with is an eigenvector. $I-A^TA$ is symmetric, so there is an orthonormal basis $\beta=[\vec{u}_1,\ldots,\vec{u}_n]$ that consists solely of eigenvectors of $I-A^TA$. They are all unit vectors. Now, because they are unit vectors, $\vec{u}_i \cdot (I-A^TA)\vec{u}_i = 0$. But $\vec{u}_i$ is an eigenvector of $I-A^TA$; what is the corresponding eigenvalue? This works for $i=1,\ldots,n$. What does that tell you about $I-A^TA$?2011-03-12
  • 0
    @Arturo: So if I understand correctly, it is a property of any symmetric matrix that it has an orthonormal eigenbasis. So then $\vec{u}_i \cdot (I-A^TA)\vec{u}_i = 0$ and the corresponding eigenvalue should be 1, since $(I-A^TA)$ is orthonormal (or is it? I am a bit lost). So then we get u dot u = 0? I guess I made a mistake somewhere...2011-03-12
  • 0
    @Jared: Yes, every symmetric matrix has an orthonormal eigenbase. Now, if $\vec{u}$ has eigenvalue $\lambda$, then$$0 = \vec{u}_i\cdot(I-A^TA)\vec{u}_i = \vec{u}_i\cdot\lambda\vec{u}_i = \lambda(\vec{u}_i\cdot\vec{u}_i).$$But $\vec{u}_i$ is a unit vector. So what is $\lambda$?2011-03-12
  • 0
    @Arturo: Oh ok, so the eigenvalue is zero. That means that our matrix is non-invertible, not sure if that helps. How does it help us answer the original question though? I guess if we distribute we get $(I-A^TA)$u= u-$(A^TA)$u=0, so $(A^TA)$ must have eigenvalue 1...2011-03-12
  • 0
    @Jared: The $\vec{u}_i$ are a **basis**; and they are all eigenvectors with eigenvalue $0$. What does $I-A^TA$ do to a basis then? What does that tell you about $I-A^TA$? What does *that* tell you about $A^TA$?2011-03-12
  • 0
    @Arturo: So then $I-A^TA$ sends all the basis vectors to zero, if I understand correctly. It tells me that $I-A^TA$ sends the whole domain to zero, as it sends the whole basis to zero... Sorry I am probably annoying you incredibly because I am not sure what to get at.2011-03-12
  • 0
    @Arturo: Oh I guess that tells me that $I-A^TA$ is the zero matrix, and $A^TA$=$I$ meaning $A$ is orthogonal?2011-03-12
  • 0
    @Jared: Don't guess. Say it with confidence, because it's right.2011-03-12
  • 0
    @Arturo: Thank you so much for walking me through, you have done an unbelievable job... This was also a problem somewhat harder than I would expect a practice problem to be, but it just shows that I need to squeeze out as much as I can from what I have... Thank you again.2011-03-12
  • 0
    @Arturo: Sorry to bother you again, but this conversation got me thinking -- is the identity matrix only symmetric and orthogonal matrix?2011-03-12
  • 0
    @Jared: No. For one thing, $$\left(\begin{array}{cc}0&1\\1&0\end{array}\right)$$ is not the identity, is orthogonal, and is symmetric. And so is $-I$. Among others. They are pretty restricted, but not quite *that* restricted.2011-03-12
0

For question 4, write down the matrix product in summation form. It can be found here: http://en.wikipedia.org/wiki/Matrix_multiplication. Then, set one matrix to the transpose of the other. It can be found here: http://en.wikipedia.org/wiki/Transpose. Then, you will notice in the summation that a*b = b*a, thus you will find $B = A*A^T \iff B_{ij} = B_{ji} \iff B = B^T$

  • 1
    Thanks, I have figured out that $(AA^{T})^{T}=(A^{{T}^{T}}A^{T})=(AA^{T})$, so they are symmetric.2011-03-12