Mathematical Food for Thought


			Mathematical Food for Thought

google
yahoo
bing

About
Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.

Meta
- Register
- Log in
- Valid XHTML
- XFN
- WordPress

Credits
- Design by Stacee Leung
- Coded by Daynah Nguyen
- Powered by Wordpress

The Matrix?! Topic: Calculus/Linear Algebra.	November 18th, 2006
Definition: A square matrix is diagonalizable if there exist matrices such that is invertible, is diagonal (has only entries on the main diagonal), and $A = VDV^{-1}$ . ——————– Problem: Solve the differential equation $x^{\prime}(t) = Ax(t)$ where is a diagonalizable $n \times n$ square matrix and is a vector valued function (which must have components). Solution: Well this is a lot like the regular differential equation $y^{\prime} = ky$ which has solution $y = y_0 e^{kt}$ . So let’s guess that $x(t) = e^{At}x(0)$ is the solution. But what exactly does $e^{At}$ mean? Consider the following. ——————– Definition: If is a function and is a diagonal square matrix, then we say that is simply the matrix with applied to all the elements on the diagonal. If is diagonalizable, then we have $A = VDV^{-1}$ and we define $f(A) = Vf(D)V^{-1}$ . ——————– So does $x(t) = e^{At}x(0)$ work as a solution to the differential equation? It turns out that, by using the definition of the derivative we can show that $\frac{d}{dt}[e^{Dt}] = De^{Dt}$ and $\frac{d}{dt}[e^{At}x(0)] = VDe^{Dt}V^{-1}x(0)$ . However, if we use the function $g(x) = xe^{xt}$ , we get $Ae^{At}x(0) = g(A)x(0) = Vg(D)V^{-1}x(0) = VDe^{Dt}V^{-1}x(0)$ , so $x^{\prime}(t) = \frac{d}{dt}[e^{At}x(0)] = Ae^{At}x(0) = Ax(t)$ , as desired. QED. ——————– Comment: Applying functions to matrices is a super cool thing and being able to solve differential equations with matrix coefficients is even better. Linear algebra provides all sorts of new ways to work with matrices. ——————– Practice Problem: Show that all symmetric square matrices are diagonalizable. Posted in Calculus, Linear Algebra \|\| No Comments »
Simon Says Factor. Topic: Linear Algebra.	November 12th, 2006
Problem: (2003 IMC Day 2 – #1) Let and be $n \times n$ real matrices such that . Prove that . Solution: Well, seeing the , we think Simon’s Favorite Factoring Trick. But, we have to remember that we’re working with matrices, not numbers. So instead of , we have , where is the $n \times n$ identity matrix (the equivalent of in the matrix world). Recall that for any square matrix we have (where is the identity matrix of corresponding size), so from the given condition. But the equation means that and are inverses of each other. Which consequently means we can multiply them in either order. So $AB+B+A+I_n = BA+A+B+I_n \Rightarrow AB = BA$ as desired. QED. ——————– Comment: Just basic algebraic manipulations if you knew several key properties of matrices and recognized the factoring. Always good to keep these things handy! ——————– Practice Problem: (1999 IMC Day 1 – #1) Show that for all natural numbers there exists a real $n \times n$ matrix such that . Furthermore, prove that for all such . [Reworded] Posted in Linear Algebra \|\| No Comments »
Dimensions Everywhere. Topic: Linear Algebra.	November 9th, 2006
Problem: (1998 IMC Day 1 – #1) Let be a -dimensional real vector space and two linear subspaces such that $U_1 \subseteq U_2$ , $\dim U_1 = 3$ , and $\dim U_2 = 6$ . Let $\epsilon$ be the set of linear maps $T: V \rightarrow V$ which have $T(U_1) \subseteq U_1$ and $T(U_2) \subseteq U_2$ . Calculate the dimension of $\epsilon$ . Solution: Well we have a total of $10 \cdot 10 = 100$ degrees of freedom without the constraints. The constraint $T(U_1) \subseteq U_1$ takes away $3 \cdot 7 = 21$ (since all three dimensions of have to map to ), while the constraint $T(U_2) \subseteq U_2$ takes away an additional $3 \cdot 4 = 12$ (since the remaining three dimensions of have to map to ). Hence the total number of dimensions of linear maps is . QED. ——————– Comment: A pretty standard problem on linear transformations and linear algebra. Easy by most standards, since it really only involves some simple calculations. ——————– Practice Problem: What is the dimension of the span of the vectors , , and ? Posted in Linear Algebra \|\| No Comments »
Rank Me! Topic: Linear Algebra.	November 7th, 2006
Problem: (2005 IMC Day 1 – #1) Let be a matrix such that $A_{ij} = i+j$ . Find the rank of . Solution: Well we clearly have the th row of the matrix equal to $R_k = (k+1, k+2, \ldots, k+n)$ . So we just need to reduce this to row-echelon form through elementary operations. Well, we can take $R_k \rightarrow R_k-R_{k-1}$ for $k \ge 2$ , so we now have $R_1 = (2, 3, \ldots, n+1)$ and $R_k = (1, 1, \ldots 1)$ for $k \ge 2$ . Now for all , take $R_k \rightarrow R_k-R_2$ and take $R_1 \rightarrow R_1-2R_2$ so our matrix becomes $R_1 = (0, 1, \ldots, n-1)$ , $R_2 = (1, 1, \ldots, 1)$ , and $R_k = (0, 0, \ldots, 0)$ for . Swapping and gives us row-echelon form, from which we can easily see that there are two pivot elements, which means the rank of is two. Note that for the rank is one. QED. ——————– Comment: Really not a difficult problem if you know any fundamental linear algebra and the operations you can perform on a matrix to calculate its rank. Linear algebra is super cool and even useful on competitions (when you get to college)! ——————– Practice Problem: For any matrix , prove that $\text{rank}(A) = \text{rank}(A^T)$ . Posted in Linear Algebra \|\| No Comments »
It’s A One-To-One Tie! Topic: Linear Algebra.	May 26th, 2006
Note: Added my linear algebra book to the Math Books page. ——————– Definition: A function $f: A \to B$ is linear if and for $x,y \in A$ and $c \in \mathbb{R}$ (or, rather, any field $\mathbb{F}$ ). Furthermore, it is one-to-one if and only if $f(x) = f(y) \Rightarrow x = y$ . ——————– Problem: Let and be vector spaces, and let $T: V \to W$ be linear. Then is one-to-one if and only if carries linearly independent subsets of onto linearly independent subsets of . Solution: First we will show that if is one-to-one, then it carries linearly independent subsets of onto linearly independent subsets of . Let be a linearly independent subset of . Suppose $S = \{x_1, x_2, \ldots, x_k\}$ . We want to show that $R = \{T(x_1), T(x_2), \ldots, T(x_k)\}$ is also linearly independent. Suppose that is not. Then there exist $a_1, a_2, \ldots, a_k$ not all zero such that $a_1T(x_1)+a_2T(x_2)+\cdots+a_kT(x_k) = 0$ . Since is linear, we can rewrite this as $T(a_1x_1)+T(a_2x_2)+\cdots+T(a_kx_k) = T(a_1x_1+a_2x_2+\cdots+a_kx_k) = 0$ . Since and is one-to-one, we must have $a_1x_1+a_2x_2+\cdots+a_kx_k = 0$ . But is linearly independent, so this is only possible if $a_1 = a_2 = \cdots = a_k = 0$ , a contradiction. So is linearly independent. Now, we will prove the converse – if takes linearly independent subsets of to linearly independent subsets of then is one-to-one. Let $x, y \in V$ be nonzero such that . It suffices to show that . If $\{x, y\}$ is linearly dependent, then for some $c \in \mathbb{R}$ , so . If $T(x) = T(y) \neq 0$ , we have $c = 1 \Rightarrow x = y$ . In the case that , the set $\{x\}$ is linearly independent but takes it onto $\{0\}$ , which is linearly dependent, a contradiction. If $\{x, y\}$ is linearly independent, then $\{T(x), T(y)\}$ is also linearly independent. But since , the set is clearly linearly dependent, a contradiction. Lastly, we have . So must be a one-to-one function, as desired. QED. ——————– Comment: Basically, we made extensive use of the properties of a linear transformation to prove both directions. A nice corollary to this proof is that if is one-to-one, then is linearly independent if and only if is linearly independent. ——————– Practice Problem: Let and be vector spaces, and let $T: V \to W$ be linear. Then is one-to-one if and only if $N(T) = \{0\}$ (here, is the kernal of , defined by $N(T) = \{x \| T(x) = 0\}$ ). Posted in Linear Algebra \|\| No Comments »

free web counters