Raising the bar

Review of mt3042 Optimization Guide by M. Baltovic

by Kairat Mynbaev, professor, ISE, KBTU, Almaty, Kazakhstan

This is a one-semester course in Optimization. It covers the following topics:

• Introduction and review of relevant parts from real analysis, with emphasis on higher dimensions.
• Weierstrass' Theorem on continuous functions on compact sets.
• Review with added rigour of unconstrained optimization of differentiable functions.
• Lagrange's Theorem on equality-constrained optimization.
• The Kuhn-Tucker Theorem on inequality-constrained optimization.
• Finite and infinite horizon dynamic programming.

The course is based mainly on the book by Sundaram, L.R. A First Course in Optimization Theory. (Cambridge University Press, 1996).

The course is given to fourth year students. I evaluate the guide on two points: how well it expands the students’ theoretical horizon and how well it prepares them to the challenges they may face while applying their knowledge in their careers, whether in industry or in academia.

1. The exposition is overly formal. Experience shows that most students don’t understand the definition of continuity in terms of epsilon-delta. Right after giving it on p.18, the author gives an alternative definition in terms of sequences. I think it’s better to omit the former definition altogether and rephrase everything in terms of sequences. After all, the compactness notion relies on sequences.
2. The differentiability definition 2.21 on p.19 is simply indigestible. It is in fact the Fréchet derivative applicable in the infinite-dimensional case. Who needs it here? Why not define the matrix as a matrix of partial derivatives, which students know from previous courses?
3. The solution to Example 3.2 is overblown. A professional mathematician never thinks like that. A pro would explain the idea as follows: because of Condition 2, the function is close to zero in some neighborhood of infinity. Therefore, a maximum should be looked for in a bounded closed set. Since this is a compact, the Weierstrass theorem applies. With a proper graphical illustration, the students don’t need anything else. Remarks similar to this apply to many solutions in the guide. As a result, the students don’t see the forest behind the trees.
4. Regarding the theoretical conditions, the author refers to Sundaram without explaining why they are imposed. Explanations in Sundaram are far from intuitive (see the first of them on p.107). In all cases for n=2 it is possible to give relatively simple intuitive explanations. Specifically,
   1. For first-order conditions see
      https://raisingthebar.nl/2017/10/11/unconstrained-optimization-plane-1/.
   2. For second-order conditions see
      https://raisingthebar.nl/2017/10/14/unconstrained-optimization-on-the-plane-2/.
   3. For the constraint qualification condition, see
      https://raisingthebar.nl/2017/10/21/importance-implicit-function-theorem-optimization/.
      The explanation on pp.58-60 is hard to understand because of dimensionality.
   4. For the Lagrange method see
      https://raisingthebar.nl/2017/10/23/lagrange-method-necessary-condition/
      (necessary conditions),
      https://raisingthebar.nl/2017/10/23/lagrange-method-sufficient-conditions/
      (sufficient conditions),
      https://raisingthebar.nl/2017/10/27/lagrange-method-case-many-equality-constraints/
      (case of many constraints) and
      https://raisingthebar.nl/2017/10/28/lagrangian-multiplier-interpretation/
      (multiplier interpretation).
   5. In case of the Kuhn-Tucker theorem, the most important point is that, once the binding constraints have been determined, the nonbinding ones can be omitted from the analysis
      https://raisingthebar.nl/2017/10/29/the-kuhn-tucker-theorem-ins-and-outs/.
      The proof of nonnegativity of the Lagrange multiplier for binding constraints is less than one page:
      https://raisingthebar.nl/2017/10/28/kuhn-tucker-theorem-first-look/.
5. In solutions that rely on the Kuhn-Tucker theorem, the author suggests to check the constraint qualification condition for all possible combinations of constraints. Not only is this time consuming, but this is also misleading, given the fact that often it is possible to determine the binding constraints and use the Lagrange method instead of the Kuhn-Tucker theorem.
6. Minor remark: In Example 5.2, the function $latex f(x,1-x)$ is obviously nonnegative.
7. There are many optimization methods not covered in Sundaram’s book. One of them, Pontryagin’s maximum principle, is more general than the Bellman approach, see
   https://en.wikipedia.org/wiki/Pontryagin%27s_maximum_principle.
   It may be too advanced for this course. However, convexity is covered by Sundaram and omitted by Baltovic, while it can be successfully applied to solve some problems from the guide, see
   https://raisingthebar.nl/2017/11/08/using-convexity-optimization/.
8. Another important area that is covered neither in the book nor in the guide is numerical optimization. Numerical optimization is as important as the Maximum Likelihood method in Statistics because ML realization in any software employs numerical optimization. People need to learn at least one method in numerical optimization to understand error messages produced on the computer.
9. Speaking of applications, I would eliminate all big exercises that have nothing to do with Economics or Finance, such as Exercise 6.2.
10. In the solution to Exercise 6.1, the author produces a 3-page analysis but then in one line discovers that all that was for nothing because the profit is infinite. What’s the pedagogical value of such an exposition?

Conclusion. This is a badly written guide for a badly designed course. I suggest removing it from our program.

Elementary transformations

Here we look at matrix representations of transformations called elementary.

Exercise 1. Let $latex e_{i}$ denote the $latex i$-th unit row vector and let $latex A$ be an arbitrary matrix. Then

a) premultiplication of $latex A$ by $latex e_{j}$ cuts out of $latex A$ the $latex j$-th row $latex A_{j}.$

b) Premultiplication of $latex A$ by $latex e_{i}^{T}e_{j}$ puts the row $latex A_{j}$ into the $latex i$-th row of the null matrix.

c) Premultiplication of $latex A$ by $latex I+ce_{i}^{T}e_{j}$ adds row $latex A_{j}$ multiplied by $latex c$ to row $latex A_{i},$ without changing the other rows of $latex A.$

d) The matrix $latex I+ce_{i}^{T}e_{j}$ has determinant 1.

Proof. a) It's easy to see that

$latex e_{j}A=\left( 0...0~1~0...0\right) \left(\begin{array}{ccc}a_{11} & ... & a_{1n} \\
... & ... & ... \\a_{j1} & ... & a_{jn} \\... & ... & ... \\a_{n1} & ... & a_{nn}\end{array}
\right) =\left(\begin{array}{ccc}a_{j1} & ... & a_{jn}\end{array}\right) =A_{j}.$

b) Obviously,

$latex e_{i}^{T}e_{j}A=\left(\begin{array}{c}0 \\... \\0 \\1 \\0 \\... \\0\end{array}
\right) \left(\begin{array}{ccc}a_{j1} & ... & a_{jn}\end{array}
\right) =\left(\begin{array}{ccc}0 & ... & 0 \\... & ... & ... \\a_{j1} & ... & a_{jn} \\... & ... & ... \\
0 & ... & 0\end{array}
\right) =\left(\begin{array}{c}\Theta \\A_{j} \\\Theta\end{array}
\right) $

($latex A_{j}$ in the $latex i$-th row, $latex \Theta$ denotes null matrices of conformable dimensions)

c) $latex (I+ce_{i}^{T}e_{j})A=A+ce_{i}^{T}e_{j}A=\left(\begin{array}{c}
A_{1} \\... \\A_{i} \\... \\A_{n}\end{array}
\right) +\left(\begin{array}{c}\Theta \\... \\cA_{j} \\... \\\Theta\end{array}
\right) =\left(\begin{array}{c}A_{1} \\... \\A_{i}+cA_{j} \\
... \\A_{n}\end{array}\right) .$

d) The matrix $latex A=I+ce_{i}^{T}e_{j}$ has ones on the main diagonal and only one nonzero element $latex a_{ij}=c$ outside it. By the Leibniz formula it's determinant is 1.

The reader can easily solve the next

Exercise 2. a) Postmultiplication of $latex A$ by $latex e_{j}^{T}$ cuts out of $latex A$ the $latex j$-th column $latex A^{(j)}.$

b) Postmultiplication of $latex A$ by $latex e_{j}^{T}e_{i}$ puts the column $latex A^{(j)}$ into the $latex i$-th column of the null matrix.

c) Postmultiplication of $latex A$ by $latex I+ce_{j}^{T}e_{i}$ adds column $latex A^{(j)}$ multiplied by $latex c$ to column $latex A^{(i)},$ without changing the other columns of $latex A.$

d) The matrix $latex I+ce_{j}^{T}e_{i}=(I+ce_{i}^{T}e_{j})^{T}$ has determinant 1.

Exercise 3. a) Premultiplication of $latex A$ by

(1) $latex \left(\begin{array}{c}e_{1} \\... \\e_{j} \\... \\e_{i} \\... \\e_{n}\end{array}
\right) $

permutes rows $latex A_{i},A_{j}.$

b) Postmultiplication of $latex A$ by the transpose of (1) permutes columns $latex A^{(i)},A^{(j)}.$

This is a general property of permutation matrices. Recall also that their determinants can be only $latex \pm 1.$

Definition. 1) Adding some row multiplied by a constant to another row or 2) adding some column multiplied by a constant to another column or 3) permuting rows or columns is called an elementary operation. Accordingly, matrices that realize them are called elementary matrices.

Law and order in the set of matrices

The law is to feel by touch every little fact. The order is discussed below.

Why do complex numbers come right before this topic?

The analog of a conjugate number is the transpose $latex A^T.$ How can you tell this? Using Exercise 2 we see that $latex (cx)\cdot {y}=x\cdot (\bar{c}y).$ This looks similar to the identity $latex (Ax)\cdot y=x\cdot(A^Ty)$ (see Exercise 4). Therefore the mapping $latex c\rightarrow \bar{c}$ is similar to $latex A\rightarrow A^{T}.$

Once you know this, it's easy to come up with a couple of ideas.

Idea 1. From the characterization of real numbers (see Equation (4)) we see that matrices that satisfy $latex A=A^T$ (symmetric matrices) correspond to real numbers and should be better in some way than asymmetric ones.

Idea 2. From Equation (3) we see that the matrix $latex A^TA$ should be symmetric and non-negative.

What is a non-negative matrix?

The set of real numbers is ordered in the sense that for any two real numbers $latex a,b$ we can say that either $latex a\geq b$ or $latex a<b$ is true. The most important property that we used in my class is this: if $latex a\geq b$ and $latex c>0,$ then $latex ac\geq bc$ (the sign of an inequality is preserved if the inequality is multiplied by a positive number). Since any two numbers can be compared like that, it is a complete order.

One way in which symmetric matrices are better than more general ones is that for symmetric matrices one can define order. The limitation caused by dimensionality is that this order is not complete (some symmetric matrices are not comparable).

Exercise 1. For the matrix $latex A=\left(\begin{array}{cc}a_{11}&a_{12}\\a_{12}&a_{22}\end{array}\right)$ and vector $latex x\in R^2$ find the expression $latex Q_A(x)=x^TAx.$ What is the value of this expression at $latex x=0?$

Solution. $latex Q_A(x)=x_1^2+2a_{12}x_1x_2+a_{22}x_2^2$ and $latex Q_A(0)=0.$

Definition 1. The function $latex Q_A(x)=x^TAx$ is called a quadratic form of the matrix $latex A.$ Here $latex A$ is symmetric of size $latex n\times n$ and $latex x\in R^n.$

Discussion. 1) The facts that $latex A$ is in the subscript and the argument is $latex x$ mean that $latex A$ is fixed and $latex x$ is changing.

2) While the argument is a vector, the value of this function is a real number: $latex Q_A$ acts from $latex R^n$ to $latex R.$

3) $latex Q_A(x)$ does not contain constant or linear terms (of type $latex c$ and $latex ax_i).$ It contains only quadratic terms (write $latex x_1x_2=x_1^1x_2^1$ to see that the total power is 2), that's why it is called a quadratic form and not a quadratic function.

Definition 2. We say that $latex A$ is positive if $latex Q_A(x)>0$ for all nonzero $latex x\in R^n$ and non-negative if $latex Q_A(x)\geq 0$ for all $latex x\in R^n.$ (Most sources say positive definite instead of just positive and non-negative definite instead of just non-negative. I prefer a shorter terminology. If you don't understand why in the definition of positivity we require nonzero $latex x,$ go back to Exercise 1). As with numbers, for two symmetric matrices $latex A,B$ of the same size, we write $latex A>B$ or $latex A\geq B$ if $latex A-B$ is positive or non-negative, respectively. Continuing this idea, we can say that $latex A$ is negative if $latex -A$ is positive.

More on motivation. A legitimate definition of order $latex A\geq B$ would obtain if we compared the two matrices element-wise. Definition 2 is motivated by the fact that quadratic forms arise in the multivariate Taylor decomposition.

Sylvester's criterion is the only practical tool for determining positivity or non-negativity. However, in one case this is simple.

Exercise 2. Show that $latex A^TA$ is symmetric and non-negative.

Solution. The symmetry is straightforward and has been shown before. Non-negativity is not difficult either: $latex Q_{A^TA}(x)=x^TA^TAx=(Ax)^TAx=\|Ax\|^2\ge 0.$

Geometry

The graph of a quadratic form in good cases is an elliptic paraboloid and has various other names in worse cases. Geometrically, the definition of the inequality $latex A\geq B$ means that the graph of $latex A$ is everywhere above the graph of $latex B$ (at the origin they always coincide). In particular, $latex A\geq 0$ means that the graph of $latex A$ is everywhere above the horizontal plane.

Examples. All examples are matrices of size $latex 2\times 2$.

Figure 1. Quadratic form of identity (elliptic paraboloid)

1) The identity matrix $latex I$ is positive because $latex Q_I(x)=x_1^2+x_2^2$, see Figure 1.

Figure 2. Parabolic cylinder

2) The matrix $latex A=\left(\begin{array}{cc}1&0\\0&0\end{array}\right)$ is non-negative. Its quadratic form $latex Q_A(x)=x_1^2$ grows when $latex |x_1|$ grows and stays flat when $latex x_2$ changes and $latex x_1$ is fixed, see Figure 2.

Figure 3. Hyperbolic paraboloid

3) The matrix $latex B=\left(\begin{array}{cc}1&0\\0&-1\end{array}\right)$ is not positive or non-negative or negative or non-positive. Its quadratic form $latex Q_B(x)$$latex =x_1^2-x_2^2$ is a parabola with branches looking upward when the second argument is fixed and a parabola with branches looking downward when the first argument is fixed, see Figure 3. When a surface behaves like that around some point, that point is called a saddle point.

Summary and questions for repetition

I was planning to cover the Moore-Penrose inverse which allows one to solve the equation $latex Ax=y$ for any $latex A$ (not necessarily square). Now my feeling is that it would be too much for a standard linear algebra course. This is the most easily accessible sourse.

1. Give the definition and example of an orthonormal system. Prove that elements of such a system are linearly independent.

2. "To know how a matrix acts on vectors, it is enough to know how it acts on the elements of an orthonormal basis." Explain.

3. How can you reveal the elements of a matrix $latex A$ from $latex (Ax)\cdot y$?

4. A linear mapping from one Euclidean space to another generates a matrix. Prove.

5. Prove that an inverse of a linear mapping is linear.

6. What is a linear mapping in the one-dimensional case?

7. In case of a square matrix, what are the four equivalent conditions for the equation $latex Ax=y$ to be good (uniquely solvable for all $latex y$)?

8. Give two equivalent definitions of linear independence.

9. List the simple facts about linear dependence that students need to learn first.

10. Prove the criterion of linear independence.

11. Let the vectors $latex x^{(1)},...,x^{(k)}$ be linearly dependent and consider the regression model $latex y=\beta_1x^{(1)}+...+\beta_kx^{(k)}+u.$ Show that here the coefficients $latex \beta_1,...,\beta_k$ cannot be uniquely determined (this is a purely algebraic fact, you don't need to know anything about multiple regression).

12. Define a basis. Prove that if $latex x^{(1)},...,x^{(k)}$ is a basis and $latex x$ is decomposed as $latex x=a_1x^{(1)}+...+a_kx^{(k)},$ then the coefficients $latex a_1,...,a_k$ are unique. Prove further that they are linear functions of $latex x.$

13. Prove that the terms in the orthogonal sum of two subspaces have intersection zero.

14. Prove dimension additivity.

15. Prove that a matrix and its transpose have the same rank.

16. Prove the rank-nullity theorem.

17. Prove the upper bound on the matrix rank in terms of the matrix dimensions.

18. Vectors are linearly independent if and only if one of them can be expressed as a linear combination of the others.

19. What can be said about linear (in)dependence if some vectors are added to or removed from the system of vectors?

20. Prove that if the number of vectors in a system is larger than the space dimension, then such a system is linearly dependent.

21. Give a list of all properties of rank that you've learned so far.

22. Prove the inequality $latex \text{rank}(AB)\le \min\{\text{rank}(A),\text{rank}(B)\}$ and use it to give an alternative proof of the rank-nullity theorem.

23. Prove that the definition of the space dimension does not depend on the basis used.

Rank of a matrix and the rank-nullity theorem

If you find proofs shorter than mine, shoot me an email.

Rank and its properties

Definition 1. The dimension of the image $latex \text{Img}(A)$ is called a rank of the matrix $latex A$ and denoted $latex \text{rank}(A)$.

Exercise 1. For any matrix $latex A$

(1) $latex \text{rank}(A)=\text{rank}(A^{T}).$

Proof. Suppose $latex A$ is of size $latex n\times k$. We know that

(2) $latex R^k=N(A)\oplus\text{Img}(A^T).$

By (2) any $latex x\in R^k$ can be represented as

(3) $latex x=y+z,$ with $latex y\in N(A),$ $latex z\in\text{Img}(A^T)$ and $latex y\perp z.$

From (3) $latex Ax=Ay+Az=Az.$ By Definition 1, $latex \text{Img}(A^T)$ is spanned by some linearly independent vectors $latex z^{(1)},...,z^{(m)}$ with $latex m=\dim\text{Img}(A^T).$ Hence $latex z=\sum_{i=1}^ma_iz^{(i)}$ with some $latex a_i$ depending on $latex z$ and $latex Ax=\sum_{i=1}^ma_iAz^{(i)}.$ This shows that $latex \text{Img}(A)$ is spanned by $latex Az^{(1)},...,Az^{(m)}.$ If we prove linear independence of these vectors, (1) will follow.

Suppose $latex \sum_{i=1}^mb_iAz^{(i)}=0$ with some $latex b_{i}.$ Then $latex A\left(\sum_{i=1}^mb_iz^{(i)}\right)=0.$ This tells us that $latex \sum_{i=1}^mb_iz^{(i)}\in N(A).$ Since the vector $latex \sum_{i=1}^mb_iz^{(i)}$ also belongs to $latex \text{Img}(A^T),$ by Exercise 3 it is zero. By linear independence, $latex \sum_{i=1}^mb_iz^{(i)}=0$ is possible only when $latex b_1=...=b_m=0.$ This proves the linear independence of $latex Az^{(1)},...,Az^{(m)}$ and the statement.

Exercise 2 (rank-nullity theorem) If $latex A$ is $latex n\times k,$ then $latex \dim N(A)+\dim \text{Img}(A)=k.$

Proof. Exercise 4 and equation (2) imply $latex k=\dim N(A)+\dim\text{Img}(A^T).$ But we know from Exercise 1 that $latex \dim\text{Img}(A^T)=\dim\text{Img}(A).$

Exercise 3. Let $latex A$ be of size $latex n\times k.$ Then $latex \text{rank}(A)\leq\min\{n,k\}.$

Proof. From Exercise 2 we see that $latex \text{rank}(A)=\dim\text{Img}(A)\leq k.$ Applying this inequality to $latex A^T$ we get $latex \text{rank}(A)=\text{rank}(A^T)=\dim\text{Img}(A^T)\leq n.$

Basis and dimension

Definition 1. We say that vectors $latex x^{(1)},...,x^{(m)}$ form a basis in a subspace $latex L$ if 1) it is spanned by $latex x^{(1)},...,x^{(m)}$ and 2) these vectors are linearly independent. The number of vectors in the basis is called a dimension of $latex L$ and the notation is $latex \dim L.$

An orthogonal basis is a special type of a basis, when in addition to the above conditions 1)-2) the basis vectors are orthonormal. For the dimension definition to be correct, the number of vectors in any basis should be the same. We prove correctness in a separate post.

Exercise 1. In $latex R^n$ the unit vectors are linearly independent. Prove this fact 1) directly and 2) using the properties of an orthonormal system.

Direct proof. Any $latex x\in R^n$ can be represented as

(1) $latex x=x_1e_1+...+x_ne_n.$

If the right side is zero, then $latex x=0$ and all $latex x_i$ are zero.

Proof using orthonormality.  If the right side in (1) is zero, then $latex x_i=x\cdot e_i=0$ for all $latex i.$

Exercise 2. $latex \dim R^{n}=n.$

Proof. (1) shows that $latex R^n$ is spanned by $latex e_1,...,e_n.$ Besides, they are linearly independent by Exercise 1.

Definition 2. Let $latex L_1,\ L_2$ be two subspaces such that any element of one is orthogonal to any element of the other. Then the set $latex {x_1+x_2:x_1\in L_1,\ x_2\in L_2}$ is called an orthogonal sum of $latex L_1,\ L_2$ and denoted $latex L=L_1\oplus L_2.$

Exercise 3. If a vector $latex x$ belongs to both terms in the orthogonal sum of two subspaces $latex L=L_1\oplus L_2,$ then it is zero. This means that $latex L_1\cap L_2={0}.$

Proof. This is because any element of $latex L_1$ is orthogonal to any element of $latex L_2,$ so $latex x$ is orthogonal to itself, $latex 0=x\cdot x=|x|^2$ and $latex x=0.$

Exercise 4 (dimension additivity) Let $latex L=L_1\oplus L_2$ be an orthogonal sum of two subspaces. Then $latex \dim L=\dim L_1+\dim L_2.$

Proof. Let $latex l_i=\dim L_i,$ $latex i=1,2.$ By definition, $latex L_1$ is spanned by some linearly independent vectors $latex y^{(1)},...,y^{(l_{1})}$ and $latex L_2$ is spanned by some linearly independent vectors $latex z^{(1)},...,z^{(l_{2})}.$ Any $latex x\in L$ can be decomposed as $latex x=y+z,$ $latex y\in L_1,$ $latex z\in L_2.$ Since $latex y,z$ can be further decomposed as $latex y=\sum_{i=1}^{l_1}a_iy^{(i)},$ $latex z=\sum_{i=1}^{l_2}b_iz^{(i)},$ the system $latex y^{(1)},...,y^{(l_1)}, z^{(1)},...,z^{(l_2)}$ spans $latex L.$

Moreover, this system is linearly independent. If

$latex \sum_{i=1}^{l_1}a_iy^{(i)}+\sum_{i=1}^{l_2}b_iz^{(i)}=0,$

then

$latex L_1\ni\sum_{i=1}^{l_1}a_iy^{(i)}=-\sum_{i=1}^{l_2}b_iz^{(i)}\in L_2.$

By Exercise 3 then $latex \sum_{i=1}^{l_1}a_iy^{(i)}=0,$ $latex \sum_{i=1}^{l_2}b_iz^{(i)}=0.$ By linear independence of the vectors in the two systems all coefficients $latex a_i,b_i$ must be zero.

The conclusion is that $latex \dim L=l_1+l_2.$

Linear dependence of vectors: definition and principal result

This is a topic most students have trouble with. It's because there is a lot of logic involved, so skimming it is not a good idea. We start with the most common definition.

Definition 1. Let $latex x^{(1)},...,x^{(k)}\in R^n$ be some vectors. They are called linearly dependent if there exist numbers $latex a_1,...,a_k,$ not all of which are zero, such that

(1) $latex a_1x^{(1)}+...+a_kx^{(k)}=0.$

The sheer length of this definition scares some people and all they remember is equation (1). Stating just (1) instead of the whole definition is like skinning an animal.

Seizing the bull by the horns

The first matter of business is to shorten the definition and relate it to what we already know.

It's better to join the set of numbers $latex a_1,...,a_k$ into a vector $latex a=(a_1,...,a_k).$ Then the requirement that "not all of $latex a_1,...,a_k$ are zero" is equivalent to a single equation $latex a\neq 0.$ Further, let us write the vectors $latex x^{(1)},...,x^{(k)}$ as columns and put them into a matrix $latex X=\left( x^{(1)},...,x^{(k)}\right) .$ Using multiplication of partitioned matrices we see that (1) is equivalent to

(2) $latex Xa=0$

and therefore Definition 1 is equivalent to the following.

Definition 2. Vectors $latex x^{(1)},...,x^{(k)}\in R^n$ are called linearly dependent if the homogeneous equation (2) has nonzero solutions $latex a\in R^k,$ that is, the null space of $latex X$ is not $latex \{0\}.$

Negating Definition 2 gives the definition of linear independence. Negating Definition 2 is easier than negating Definition 1.

Definition 3. Vectors $latex x^{(1)},...,x^{(k)}\in R^{n}$ are called linearly independent if $latex N(X)=\{0\}$ (for any nonzero $latex a\in R^k$ we have $latex Xa\neq 0$ or, alternatively, $latex Xa=0$ only for $latex a=0$).

Exercise 1. For any matrix $latex X,$ one has

(3) $latex N(X)=N(X^TX).$

Proof. 1) Proving that $latex N(X)\subset N(X^TX).$ If $latex a\in N(X),$ then $latex Xa=0$ and $latex X^TXa=0,$ so $latex a\in N(X^TX).$ 2) Proving that $latex N(X^TX)\subset N(X).$ If $latex a\in N(X^TX),$ then $latex X^TXa=0$ and $latex 0=(X^TXa)\cdot a=(Xa)\cdot(Xa)=\|Xa\|^2,$ so $latex a\in N(X).$

Exercise 2. $latex X^TX$ is a square symmetric matrix, for any $latex X.$

Proof. If $latex X$ is of size $latex n\times k,$ then $latex X^TX$ is $latex k\times k.$ It is symmetric: $latex (X^TX)^T=X^T(X^T)^T=X^TX.$ By the way, some students write $latex (X^TX)^{-1}=X^{-1}(X^T)^{-1}.$ You cannot do this if $latex X$ is not square.

Criterion of linear independence. Vectors $latex x^{(1)},...,x^{(k)}\in R^n$ are linearly independent if and only if $latex \det X^TX\neq 0.$

Proof. We are going to use (3). By Exercise 2, $latex A=X^TX$ is a square matrix and for a square matrix we have the equivalence $latex N(A)=\{0\}\Longleftrightarrow \det A\neq 0.$ Application of this result proves the statement.

Direct application of Definition 1 can be problematic. To prove that some vectors are linearly dependent, you have to produce $latex a_1,...,a_k$ such that Definition 1 is satisfied. This usually involves some guesswork, see exercises below. The criterion above doesn't require guessing and can be realized on the computer. The linear independence requirement is common in multiple regression analysis but not all econometricians know this criterion.

Putting some flesh on the bones

These are simple facts you need to know in addition to the above criterion.

Exercise 3. 1) Why do we exclude the case when all $latex a_1,...,a_k$ are zero?

2) What happens if among $latex x^{(1)},...,x^{(k)}$ there are zero vectors?

3) Show that in case of two non-zero vectors Definition 1 is equivalent to just proportionality of one vector to another.

Solution. 1) If all $latex a_1,...,a_k$ are zero, (1) is trivially satisfied, no matter what the vectors are.

2) If one of the vectors $latex x^{(1)},...,x^{(k)}$ is zero, the coefficient of that vector can be set to one and all others to zero, so such vectors will be linearly dependent by Definition 1.

3) Consider two non-zero vectors $latex x^{(1)},x^{(2)}.$ If they are linearly dependent, then

(4) $latex a_1x^{(1)}+a_2x^{(2)}=0$

where at least one of $latex a_1,a_2$ is not zero. Suppose $latex a_1\neq 0.$ Then $latex a_2\neq 0$ because otherwise $latex x^{(1)}$ would be zero. Hence

(5) $latex x^{(1)}=-a_2/a_1x^{(2)}=cx^{(2)}$

where the proportionality coefficient $latex c$ is not zero. Conversely, (5) implies (4) (you have to produce the coefficients).

Exercise 4. Prove that if to the system of unit vectors we add any vector $latex x\in R^n$, the resulting system will be linearly dependent.

Solvability of an equation with a square matrix

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

Dissecting the problem

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

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

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

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

(1) $latex BA=BAI=I.$

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

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

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

Collecting the pieces together

Exercise 4. The following conditions are equivalent:

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

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

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

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

$latex a^\prime)\ N(A)\neq {0},$  $latex b^\prime)\ \text{Img}(A)\neq R^k,$  $latex c^\prime)\ \det A=0,$  $latex 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 $latex R^k$ is replaced by $latex C^k$ (the set of vectors with complex coordinates).

Is the inverse of a linear mapping linear?

Orthonormal basis

Exercise 1. I) Let $latex e_j$ denote unit vectors. They possess properties

(1) $latex e_i\cdot e_j=0$ for all $latex i\neq j,$ $latex \left\Vert e_{i}\right\Vert =1$ for all $latex i.$

II) For any $latex x\in R^n$ we have the representation

(2) $latex x=\sum_jx_je_j.$

III) In (2) the coefficients can be found as $latex x_{j}=x\cdot e_{j}:$

(3) $latex x=\sum_j(x\cdot e_j)e_j.$

Proof. I) (1) is proved by direct calculation. II) To prove (2) we write

$latex x=(x_1,...,x_n)=x_1(1,0,...,0)+...+x_n(0,...,0,1)=\sum_jx_je_j.$

III) If we have (2), then it's easy to see that by (1) $latex x\cdot e_i=\sum_jx_j(e_j\cdot e_i)=x_i.$

Definition 1. Any system of vectors that satisfies (1) is called an orthonormal system. An orthonormal system is called complete if for any $latex x\in R^n$ we have the decomposition (3). Exercise 1 shows that our system of unit vectors is complete orthonormal. A complete orthonormal system is called an orthonormal basis.

Analyzing a linear mapping

Exercise 2. Let $latex A$ be a matrix of size $latex n\times k.$ Suppose you don't know the elements of $latex A$ but you know the products $latex (Ax)\cdot y$ for all $latex x,y.$ How can you reveal the elements of $latex A$ from $latex (Ax)\cdot y?$ How do you express $latex Ax$ using the elements you define?

Solution. Let us partition $latex A$ into rows and suppose the elements $latex a_{ij}$ are known. Let us try unit vectors as $latex x,y:$

(4) $latex (Ae_j)\cdot e_i=\left(\begin{array}{c}A_1e_j \\... \\A_ne_j\end{array}\right)\cdot e_i=A_ie_j=a_{ij}.$

Using (2) and (4) one can check that $latex (Ax)\cdot e_i=A_ix=\sum_ja_{ij}x_j.$ Hence, from (3) we have the answer to the second question:

(5) $latex Ax=\sum_i[\left(Ax\right)\cdot e_i]e_i=\sum_i\left(\sum_ja_{ij}x_j\right)e_i=\sum_{i,j}x_ja_{ij}e_i.$

The above calculation means that when $latex a_{ij}$ are unknown, we can define them by $latex a_{ij}=(Ae_j)\cdot e_i$ and then the action of $latex A$ on $latex x$ will be described by the last expression in (5).

We know that a mapping generated by a matrix is linear. The converse is also true: a linear mapping is given by a matrix:

Exercise 3. Suppose a mapping $latex f:R^k\rightarrow R^n$ is linear: $latex f(ax+by)=af(x)+bf(y)$ for any numbers $latex a,b$ and vectors $latex x,y.$ Then there exists a matrix $latex A$ of size $latex n\times k$ such that $latex f(x)=Ax$ for all $latex x.$

Proof. Based on (4) in our case put $latex a_{ij}=f(e_j)\cdot e_i$. Applying (3) to $latex f(x)$ we get

(6) $latex f(x)=\sum_i[f(x)\cdot e_i]e_i$

(the summation index $latex j$ is replaced by $latex i$ on purpose). Plugging (2) in (6)

$latex f(x)=\sum_i\left[f\left(\sum_jx_je_j\right)\cdot e_i\right]e_i=$ (both $latex f$ and scalar product are linear)

$latex =\sum_i\left[\left(\sum_jx_jf\left(e_j\right)\right)\cdot e_i\right]e_i=\sum_{i,j}x_j(f\left(e_j\right)\cdot e_i)e_i$$latex =\sum_{i,j}x_ja_{ij}e_i=Ax.$

The last equation is the definition of $latex A$.

Exercise 4. An inverse of a linear mapping is linear (and given by a matrix by Exercise 3).

Proof. Let $latex f(x)=Ax$ be a linear mapping and suppose its inverse $latex f^{-1}$ in the general sense exists. Then $latex f^{-1}(Ax)=x$ for all $latex x.$ Let us put $latex x=ay+bz$ for arbitrary numbers $latex a,b$ and vectors $latex y,z.$ Then we have $latex f^{-1}(A(ay+bz))=ay+bz$ or, using linearity of $latex A,$

$latex f^{-1}(aAy+bAz)=ay+bz.$

Putting $latex Ay=u,$ $latex Az=v$ we get

$latex f^{-1}(au+bv)=af^{-1}(u)+bf^{-1}(v).$

Thus, $latex f^{-1}$ is linear.

Remark. In all of the above it is important that $latex e_j$ are unit vectors. For a different basis, the results drastically change.

Geometry of linear equations: questions for repetition

This section evolves around the concepts of linearity, linear subspaces and orthogonality. As usual, you are expected to produce at least those proofs that I give.

1. Prove linearity of the mapping generated by a matrix. This fundamental fact will have many implications. Do you think any linear mapping is generated by some matrix? Do you think a mapping inverse to a linear mapping should be linear?

2. What is the first characterization of a matrix image? In other sources it is called a column space. Later on it will be linked to the notions of linear independence and rank.

3. How would you write $latex Ax$ ($latex A$ is a matrix and $latex x$ is a vector), if $latex A$ is partitioned a) into rows and b) into columns?

4. Show that a span of some vectors is a linear subspace. Note that one- and two-dimensional examples of linear subspaces we considered are special cases of subspaces described by linear systems of equations.

5. Can spans of two different systems of vectors coincide? Give an example.

6. Show that the image and null space of a matrix are linear subspaces. This facts indicate that the subspace notion is an adequate tool for problems at hand.

7. What is the description of the set of solutions of $latex Ax=y$? It is pretty general. For example, the structure of solutions of an ordinary linear differential equation is the same.

8. Illustrate geometrically the theorem on second orthocomplement and explain why it holds.

9. What is the relationship between $latex (Ax)\cdot y$ and $latex x\cdot (A^Ty)$?

10. Derive the second characterization of matrix image.

11. What are the geometric conditions for the solvability and uniqueness of solutions of an inhomogeneous equation?