28
Jul 18

Solvability of an equation with a square matrix

category: Matrix algebra, MT3042 Optimisation theory, Optimisation theory No Comments

Solvability of an equation with a square matrix

Everywhere in this section we assume that A is square of size k\times k. The main problem is about solvability of the equation Ax=y.

Dissecting the problem

Exercise 1. If A is invertible, then N(A)=\{0\} and \text{Img}(A)=R^k.

Proof. If Ax=0, then x=A^{-1}Ax=0, so N(A)=\{0\} (you could also say that A is one-to-one). From AA^{-1}=I we have AA^{-1}x=x. This tells us that x=Ay with y=A^{-1}x. We see that any x belongs to the image of A, so \text{Img}(A)=R^k.

Exercise 2. If N(A)=\{0\}, then A is invertible.

Proof. Since A is one-to-one, we can use the inverse f^{-1} of f(x)=Ax in the general sense: f^{-1}(Ax)=x. It is defined on the image of A. We know that f^{-1} is given by some matrix B: BAx=x for all x. Hence, BAe_i=e_i for i=1,...,k. Putting these equations side by side we get

(1) BA=BAI=I.

(In detail: the identity matrix is partitioned as I=(e_1,...,e_k), so BAI =(BAe_1,...,BAe_k)=(e_1,...,e_k)=I). Thus, B is the left inverse of A, and we've seen before that for square matrices this implies existence of the right inverse, invertibility of A and the equation B=A^{-1}.

Exercise 3. If \text{Img}(A)=R^k, then A is invertible.

Proof. If \text{Img}(A)=R^k, then by the second characterization of matrix image N(A^T)=(\text{Img}(A))^{\perp}=\{0\}. Applying Exercise 2 to A^T, we see that the transpose is invertible and hence \det A=\det A^{T}\neq 0. This implies invertibility of A.

Collecting the pieces together

Exercise 4. The following conditions are equivalent:

a) N(A)=\{0\}, b) \text{Img}(A)=R^k, c) \det A\neq 0, d) A is invertible.

Proof. The equivalence c) \Longleftrightarrow d) has been established before. For the implication d) \Longrightarrow a)+b) see Exercise 1. By Exercise 2 we have a) \Longrightarrow d). By Exercise 3, b) \Longrightarrow d.

Conclusion. The condition \det A\neq 0 is the easiest to check. If it holds, then the equation Ax=y has a unique solution for any y\in R^k.

Remark 1. By negating Exercise 4, we see that the following conditions are equivalent:

a^\prime) N(A)\neq \{0\}, b^\prime) \text{Img}(A)\neq R^k, c^\prime) \det A=0, d^\prime) A^{-1} does not exists.

Remark 2. By going through the proof one can check that the result of Exercise 4 holds if R^k is replaced by C^k (the set of vectors with complex coordinates).

Post Views: 36

Leave a Reply

You must be logged in to post a comment.