Register to reply

Solving for a Surjective Matrix

by lauratyso11n
Tags: matrix, solving, surjective
Share this thread:
lauratyso11n
#1
Sep10-10, 08:56 AM
P: 8
I saw this in a book as a Proposition but I think it's an error:

Assume that the (n-by-k) matrix, [tex]A[/tex], is surjective as a mapping,

[tex]A:\mathbb{R}^{k}\rightarrow \mathbb{R}^{n}[/tex].

For any [tex]y \in \mathbb{R}^{n} [/tex], consider the optimization problem

[tex]min_{x \in \mathbb{R}^{k}}\left{||x||^2\right}[/tex]

such that [tex] Ax = y[/tex].

Then, the following hold:
(i) The transpose of [tex]A[/tex], call it [tex]A^{T}[/tex] is injective.
(ii) The matrix [tex]A^{T}A[/tex] is invertible.
(iii) etc etc etc....

I have a problem with point (ii), take as an example the (2-by-3) surjective matrix
[tex]A = \begin{pmatrix}
1 & 0 & 0\\
0 & 1 & 0
\end{pmatrix}[/tex]

[tex]A^{T}A[/tex] in this case is not invertible.

Can anyone confirm that part (ii) of this Proposition is indeed incorrect ?
Phys.Org News Partner Science news on Phys.org
Scientists develop 'electronic nose' for rapid detection of C. diff infection
Why plants in the office make us more productive
Tesla Motors dealing as states play factory poker
ThirstyDog
#2
Sep10-10, 11:27 AM
P: 34
I would agree with you that part (ii) of the proposition is incorrect (unless matrices are not acting on vectors from the left).

If you look at bijection part
http://en.wikipedia.org/wiki/Bijecti...and_surjection
it reads: "If g o f is a bijection, then it can only be concluded that f is injective and g is surjective."

Working right to left with matrices and composition of functions says if A^{T}A was invertible (i.e. a bijection) then A would be injective and A^{T} would be surjective. Thus something is wrong!

[edit]
P.S. I didn't see the bit where it clearly said the matrices were acting from the left so I would say that it is definitely wrong.
[edit]
Landau
#3
Sep10-10, 12:22 PM
Sci Advisor
P: 905
Quote Quote by lauratyso11n View Post
Can anyone confirm that part (ii) of this Proposition is indeed incorrect ?
Yes, you are right. (i) is true but (ii) is false. But (ii) is true if A^TA is replaced by AA^T, so maybe it's a typo? I don't understand what "the optimization problem" has to do with this, or are the other parts of the proposition about this?

lauratyso11n
#4
Sep10-10, 12:31 PM
P: 8
Solving for a Surjective Matrix

Quote Quote by Landau View Post
Yes, you are right. (i) is true but (ii) is false. But (ii) is true if A^TA is replaced by AA^T, so maybe it's a typo? I don't understand what "the optimization problem" has to do with this, or are the other parts of the proposition about this?
The full Proposition is as follows:

Assume that the (n-by-k) matrix, [tex]A[/tex], is surjective as a mapping,

[tex]A:\mathbb{R}^{k}\rightarrow \mathbb{R}^{n}[/tex].

For any [tex]y \in \mathbb{R}^{n} [/tex], consider the optimization problem

[tex]min_{x \in \mathbb{R}^{k}}\left{\left||x|\right|^2\right}[/tex]

such that [tex] Ax = y[/tex].

Then, the following hold:
(i) The transpose of [tex]A[/tex], call it [tex]A^{T}[/tex] is injective.
(ii) The matrix [tex]A^{T}A[/tex] is invertible.
(iii) The unique optimal solution of the minimum norm problem is given by
[tex](A^TA)^{-1}A^Ty[/tex]

I have a problem with point (ii), take as an example the (2-by-3) surjective matrix
[tex]A = \begin{pmatrix}
1 & 0 & 0\\
0 & 1 & 0
\end{pmatrix}[/tex]

[tex]A^{T}A[/tex] in this case is not invertible.
lauratyso11n
#5
Sep10-10, 12:39 PM
P: 8
Quote Quote by Landau View Post
Yes, you are right. (i) is true but (ii) is false. But (ii) is true if A^TA is replaced by AA^T, so maybe it's a typo?
I don't think it's a typo as he uses this result to carry some other analysis further. The crux of it is:

[tex]\sigma\lambda = \alpha - \bf{r}[/tex]

where [tex]\sigma \in \mathbb{R}^{n-by-k}[/tex] is surjective, and [tex]\lambda \in \mathbb{R}^{k}[/tex], [tex]\alpha , \bf{r} \in \mathbb{R}^{n}[/tex].

How would you solve for [tex]\lambda[/tex] ? Isn't is critical that the 'typo' has to be correct to be able to solve for this ?

The author's solution as you might expect is [tex]\lambda = \left(\sigma^{T}\sigma\right)^{-1}\sigma^{T}\left[\alpha - \bf{r}\right][/tex].

So it's either a HUGE mistake on his part or I'm missing something. The author is actually quite insightful, and this error would be quite out of character for him.

BTW, thanks for making the effort to look at the problem. Much appreciated.
Office_Shredder
#6
Sep10-10, 01:22 PM
Emeritus
Sci Advisor
PF Gold
P: 4,500
Looking at dimension counting with your example, AtA is a 3x3 matrix, which means (AtA)-1 A wouldn't make sense even if the inverse was defined because the sizes of the matrices don't match up. On the other hand A At and A are compatible matrices which suggests that he just put the transpose on the wrong one and carried the error through.
Landau
#7
Sep10-10, 02:08 PM
Sci Advisor
P: 905
Quote Quote by lauratyso11n View Post
The author's solution as you might expect is [tex]\lambda = \left(\sigma^{T}\sigma\right)^{-1}\sigma^{T}[\alpha - \bf{r}][/tex].
This is correct provided that [itex]\sigma^{T}\sigma[/itex] is invertible, i.e. provided that [itex]\left(\sigma^{T}\sigma\right)^{-1}[/itex] makes sense.

The least square solution of Ax=y satisfies the normal equation:
[tex]A^TAx=A^Ty.[/tex]
This solution is unique if and only if [itex]A^TA[/itex] is invertible. In this case, it is given by
[tex]x=(A^TA)^{-1}A^Tb[/tex], just like the author asserts.

But [itex]A^TA[/itex] is not necessarily invertible, contrary to the proposition. Note that [itex]A^TA:\mathbb{R}^k\to\mathbb{R}^k[/itex] is bijective if and only if its rank equals k. But since [itex]A^TA[/itex] and A always have equal rank, this happens if and only if A has rank k. Since [itex]A:\mathbb{R}^k\to\mathbb{R}^n[/itex] is assumed to be surjective, it has rank n and we must have [itex]k\geq n[/itex]. So in fact, [itex]A^TA[/itex] is invertible if and only if k=n! Indeed, in your counter-example k and n are not equal.
Quote Quote by Office_Shredder View Post
which means (AtA)-1 A wouldn't make sense even if the inverse was defined because the sizes of the matrices don't match up.
This is not the expression the author uses; it is (AtA)-1 At.
Landau
#8
Sep10-10, 02:28 PM
Sci Advisor
P: 905
Perhaps you could post a link to the book?
Office_Shredder
#9
Sep10-10, 06:25 PM
Emeritus
Sci Advisor
PF Gold
P: 4,500
Quote Quote by Landau View Post
This is not the expression the author uses; it is (AtA)-1 At.
I assumed the * was just referring to matrix multiplication
Landau
#10
Sep10-10, 07:13 PM
Sci Advisor
P: 905
I assumed * means adjoint, so (in this real case) the transpose. This is also what lauratyso11n writes in post #5 (where A is called sigma).
lauratyso11n
#11
Sep10-10, 08:14 PM
P: 8
Quote Quote by Office_Shredder View Post
I assumed the * was just referring to matrix multiplication
Quote Quote by Landau View Post
I assumed * means adjoint, so (in this real case) the transpose. This is also what lauratyso11n writes in post #5 (where A is called sigma).
SORRYYYYYY, the [tex]A^*[/tex] is actually an [tex]A^T[/tex]. I've corrected it.
lauratyso11n
#12
Sep12-10, 01:37 PM
P: 8
The correct statement is that if [tex]A[/tex] is surjective then [tex]A^T[/tex] is injective and [tex]AA^T[/tex] is invertible.

The formula for the optimal [tex]x[/tex] is

[tex]\hat{x}=A^T(AA^T)^{-1}y[/tex]
Landau
#13
Sep12-10, 01:43 PM
Sci Advisor
P: 905
Quote Quote by lauratyso11n View Post
The correct statement is that if [tex]A[/tex] is surjective then [tex]A^T[/tex] is injective and [tex]AA^T[/tex] is invertible.
So it was a typo :)
Quote Quote by Landau View Post
Yes, you are right. (i) is true but (ii) is false. But (ii) is true if A^TA is replaced by AA^T, so maybe it's a typo?


Register to reply

Related Discussions
[MATLAB] matrix solving question Programming & Computer Science 0
Matrix - solving linear system Calculus & Beyond Homework 3
Solving 3x3 Matrix of DEs Calculus & Beyond Homework 7
Solving for the Determinent of a Matrix Linear & Abstract Algebra 16
Solving a matrix problem Calculus & Beyond Homework 1