RREF Matrices
Homogenous System
\begin{aligned} \Cmatrix{4}{2 & -1 & 3 & 2\\1&4&0&-1\\2&6&-1&5} \Ematrix{\optwo{1}{-2}{2} \\ \optwo{3}{-2}{2}} \Cmatrix{4}{0&-9&3&-5\\1&4&0&-1\\0&-2&-1&7} \Ematrix{\opone{-1/2}{3}} \Cmatrix{4}{0&-9&3&-5\\1&4&0&-1\\0&1&\frac{1}{2}&-\frac{7}{2}}\\ \Ematrix{\optwo{1}{9}{3} \\ \optwo{2}{-4}{3}} \Cmatrix{4}{0&0&\frac{15}{2}&-\frac{55}{2}\\1&0&-2&13\\0&1&\frac{1}{2}&-\frac{7}{2}} \Ematrix{\opone{2/15}{1}} \Cmatrix{4}{0&0&1&-\frac{11}{3}\\1&0&-2&13\\0&1&\frac{1}{2}&-\frac{7}{2}} \Ematrix{\optwo{2}{2}{1} \\ \optwo{3}{-1/2}{1}} \Cmatrix{4}{0&0&1&-\frac{11}{3}\\1&0&0&\frac{17}{3}\\0&1&0&-\frac{5}{3}} \end{aligned}
- Hoffman Ch 1. pg 8 Ex 5 Consider the following system of equations over
Hence, by theorem 1.2, the following system will have the same solution space as the one above!
If we examine the system, we can notice that we have three bound variables, and 1 free variable, . Now if we choose a constant , we can form the set of all solutions to the system by making . Hence the solution space will consist of all n-tuples of the form can be generalized to be
General system
\begin{aligned} \Cmatrix{cccc|c}{0&0&2&4&y_1\\1&2&0&3&y_2\\1&2&-1&-1&y_3\\2&4&1&10&y_4} \xrightarrow{r_1\iff r_2} \Cmatrix{cccc|c}{1&2&0&3&y_2\\0&0&2&4&y_1\\1&2&-1&-1&y_3\\2&4&1&10&y_4} \Ematrix{\optwo{3}{-1}{1}\\ \optwo{4}{-2}{1}} \Cmatrix{cccc|c}{1&2&0&3&y_2\\0&0&2&4&y_1\\0&0&-1&-4&y_3-y_2\\0&0&1&4&y_4-2y_2}\\ \Ematrix{\opone{1/2}{2}} \Cmatrix{cccc|c}{1&2&0&3&y_2\\0&0&1&2&\frac{1}{2}y_1\\0&0&-1&-4&y_3-y_2\\0&0&1&4&y_4-2y_2} \Ematrix{\optwo{3}{1}{2}\\ \optwo{4}{-1}{2}} \Cmatrix{cccc|c}{1&2&0&3&y_2\\0&0&1&2&\frac{1}{2}y_1\\0&0&0&-2&y_3-y_2 + \frac{1}{2}y_1\\0&0&0&2&y_4-2y_2-\frac{1}{2}y_1}\\ \Ematrix{\opone{-1/2}{3}} \Cmatrix{cccc|c}{1&2&0&3&y_2\\0&0&1&2&\frac{1}{2}y_1\\0&0&0&1&-\frac{1}{2}y_3 + \frac{1}{2}y_2 - \frac{1}{4}y_1\\0&0&0&2&y_4-2y_2-\frac{1}{2}y_1} \Ematrix{\optwo{4}{-2}{3}} \Cmatrix{cccc|c}{1&2&0&3&y_2\\0&0&1&2&\frac{1}{2}y_1\\0&0&0&1&-\frac{1}{2}y_3 + \frac{1}{2}y_2 - \frac{1}{4}y_1\\0&0&0&0&y_4 + y_3-3y_2} \end{aligned}Therefore, we can see that we have 3 bound variables, and 1 free variable, , therefore, we can only express a general solution if the following condition is held. If it is not equal to zero, then the system is inconsistent and is not solvable! Hence, if we choose a constant , we can form a general solution for the equation being:
Change of Basis Matrix
Let such that we can define the system in the following way:
Lets first try to imagine the . To do so, just imagine trying to solve A as a homogenous system, or let
x_1 & - & 2x_2& = & 0\\ -x_1 & + & 2x_2&= &0\\ 2x_1 & - & 4x_2& = & 0\\ \end{matrix}$$ Using RREF, or easily observing the fact that the second equation is twice the first, we get the value of $(2, 1)$, hence the kerT iskerT = span(\begin{bmatrix} 2 \ 1\end{bmatrix})
Now lets examine the $ImT$ We can easily observe that $$ImT = span( \begin{bmatrix} 1 \\ -1\\2\end{bmatrix}, \begin{bmatrix} -2\\ 2 \\ -4\end{bmatrix})$$ Using the image and kernal, we can then construct a basis for $\R^2$ and $\R^3$ with respect to this transformation. To find the basis of $\R^2$, pick a vector in the span of the image, lets choose $\begin{bmatrix} 1 \\ -1\\2\end{bmatrix}$. We need to find the preimage of $\begin{bmatrix} 1 \\ -1\\2\end{bmatrix}$. This is simple, go back to our system, and solve $(x_1, x_2)$ such that $$\begin{matrix} x_1 & - & 2x_2& = & 1\\ -x_1 & + & 2x_2&= &-1\\ 2x_1 & - & 4x_2& = & 2\\ \end{matrix}$$, Our value is (1, 0). Using theorem "1", we can construct a basis in using the image and the kernal, meaning that $$Basis = (\begin{bmatrix} 1 \\ 0\end{bmatrix}, \begin{bmatrix} 2 \\ 1\end{bmatrix})$$ We can also construct a basis for $\R^3$ in the following way, take the vector we choose earlier, and find two more linearly independent vectors (can be of any type, as long as all three span $\R^3$). Hence a basis of $\R^3$ is :Basis = \left{\begin{bmatrix} 1 \ -1\2\end{bmatrix}, \begin{bmatrix} 1 \ 0\0\end{bmatrix}, \begin{bmatrix} 0\ 1\0\end{bmatrix}\right}
Lets do an example, lets take vector $(3, 4)$. Then $T((3, 4)) = (-5, 5, -10)$. To see this visually, look below! ```tikz \usepackage{tikz-3dplot} \tdplotsetmaincoords{70}{110} \begin{document} \begin{tikzpicture}[scale = .5, cap = round] \draw[->] (-1, 0) -- (5, 0) node[left] {$x_1$}; \draw[->] (0, -1) -- (0, 5) node[right] {$x_2$}; \draw[orange, ->, style = very thick] (0, 0) -> (-4, 0) node[left] {$-5 \cdot (1, 0)$}; \draw[orange, ->, style = very thick] (-4, 0) -> (3, 4) node[midway, above] {$4 \cdot (4, 2) \qquad$}; \draw[red, ->, style = very thick] (0, 0) -> (1, 0) node[right] {$(1, 0)$}; \draw[red, ->, style = very thick] (0, 0) -> (2, 1) node[right] {$(2, 1)$}; \draw[teal, ->, style = very thick] (0, 0) -> (3, 4) node[right] {$(3, 4)$}; \end{tikzpicture} \begin{tikzpicture}[scale=1,tdplot_main_coords] \draw[->] (-2, 0, 0) -- (2, 0, 0) node[left] {$y_1$}; \draw[->] (0, -2, 0) -- (0, 2, 0) node[right] {$y_2$}; \draw[->] (0, 0, -2) -- (0, 0, 2) node[right] {$y_3$}; \draw[red, ->, style = very thick] (0, 0) -> (1, -1, 2) node[right] {$(1, -1, 2)$}; \draw[teal, ->, style = very thick] (0, 0) -> (-2, 2, -4) node[right] {$-5 \cdot (1, -1, 2)$}; \end{tikzpicture} \end{document} ``` > [!note]- The choice of vector from $ImT$ is not unique (you can choose any vector in the set and it will work!) > Suppose we took vector $\begin{bmatrix} -2\\ 2 \\ -4\end{bmatrix}$, then our bases would be > $$ > \left\{\begin{bmatrix} 0 \\ 1\end{bmatrix} , \begin{bmatrix} 2 \\ 1\end{bmatrix}\right\} > $$ > $$ > \left\{\begin{bmatrix} -2 \\ 1\\-4\end{bmatrix}, \begin{bmatrix} 1 \\ 0\\0\end{bmatrix}, \begin{bmatrix} 0\\ 1\\0\end{bmatrix}\right\} > $$ > Our transformation of vector $\begin{bmatrix} 3\\ 4\end{bmatrix}$ now looks like this! > >```tikz >\usepackage{tikz-3dplot} >\tdplotsetmaincoords{70}{110} > \begin{document} > \begin{tikzpicture}[scale = .5, cap = round] > \draw[->] (-1, 0) -- (5, 0) node[left] {$x_1$}; > \draw[->] (0, -1) -- (0, 5) node[right] {$x_2$}; > \draw[red, ->, style = very thick] (0, 0) -> (0, 3/2) node[left] {$5/2 \cdot (0, 1)$}; > \draw[red, ->, style = very thick] (0, 3/2) -> (3, 4) node[midway, above] {$3/2 \cdot (2, 1) \qquad$}; > \draw[orange, ->, style = very thick] (0, 0) -> (0, 1); > \node[orange] at (-1, 0) {(0, 1)}; > \draw[orange, ->, style = very thick] (0, 0) -> (2, 1) node[right] {$(2, 1)$}; > \draw[teal, ->, style = very thick] (0, 0) -> (3, 4) node[right] {$(3, 4)$}; > \end{tikzpicture} > \begin{tikzpicture}[scale=1,tdplot_main_coords] > \draw[->] (-2, 0, 0) -- (2, 0, 0) node[left] {$y_1$}; > \draw[->] (0, -2, 0) -- (0, 2, 0) node[right] {$y_2$}; > \draw[->] (0, 0, -2) -- (0, 0, 2) node[right] {$y_3$}; > > \draw[teal, ->, style = very thick] (0, 0) -> (-2, 2, -4) node[right] {$5/2 \cdot (-2, 2, -4)$}; > \draw[orange, ->, style = very thick] (0, 0) -> (-1, 1, -2) node[right] {$(-2, 2, -4)$}; > \end{tikzpicture} > \end{document} > ``` >Now suppose, we choose a vector $\begin{bmatrix} -1\\ 1 \\ -2\end{bmatrix}$, its in the Image, but is not one of the vectors that construct it, So it preimage is not as trivial to find, being $\begin{bmatrix} 3\\ 1\end{bmatrix}$ >hence, our bases are : >$$ >\left\{\begin{bmatrix} -3 \\ 1\end{bmatrix} , \begin{bmatrix} 2\\1\end{bmatrix}\right\} >$$ >$$ >\left\{\begin{bmatrix} -1 \\ 1\\-2\end{bmatrix}, \begin{bmatrix} 1\\0\\0\end{bmatrix}, \begin{bmatrix} 0\\ 1\\0\end{bmatrix}\right\} >$$ >```tikz >\usepackage{tikz-3dplot} >\tdplotsetmaincoords{70}{110} > \begin{document} > \begin{tikzpicture}[scale = .5, cap = round] > \draw[->] (-1, 0) -- (5, 0) node[left] {$x_1$}; > \draw[->] (0, -1) -- (0, 5) node[right] {$x_2$}; > \draw[orange, ->, style = very thick] (0, 0) -> (-9, -3) node[left] {$5 \cdot (3, 1)$}; > \draw[orange, ->, style = very thick] (-9, -3) -> (3, 4) node[midway, above] {$9 \cdot (2, 1) \qquad$}; > \draw[red, ->, style = very thick] (0, 0) -> (-3, -1) node[left] {(3, 1)}; > \draw[red, ->, style = very thick] (0, 0) -> (2, 1) node[right] {$(2, 1)$}; > \draw[teal, ->, style = very thick] (0, 0) -> (3, 4) node[right] {$(3, 4)$}; > \end{tikzpicture} > \begin{tikzpicture}[scale=1,tdplot_main_coords] > \draw[->] (-2, 0, 0) -- (2, 0, 0) node[left] {$y_1$}; > \draw[->] (0, -2, 0) -- (0, 2, 0) node[right] {$y_2$}; > \draw[->] (0, 0, -2) -- (0, 0, 2) node[right] {$y_3$}; > > \draw[teal, ->, style = very thick] (0, 0) -> (-2, 2, -4) node[right] {$5 \cdot (-1, 1, -2)$}; > \draw[red, ->, style = very thick] (0, 0) -> (-1, 1, -2) node[right] {$(-1, 1, -2)$}; > \end{tikzpicture} > \end{document} > ``` > [!note]- Examining Equivalent Systems > Now suppose we examine the system : $$\begin{bmatrix}-3 & 6 \\ -2 & 4 \\ -2 & 4\end{bmatrix}$$ > $kerT = span(\begin{bmatrix} 2 \\ 1\end{bmatrix})$ > $ImT = span(\begin{bmatrix}-3 \\ -2 \\ -2\end{bmatrix}, \begin{bmatrix} 6 \\ 4 \\ 4\end{bmatrix})$ > $v = \begin{bmatrix}-3 \\ -2 \\ -2\end{bmatrix}$, preimage : $\begin{bmatrix}1 \\ 0\end{bmatrix}$, $T(\begin{bmatrix} 3 \\ 4\end{bmatrix}) = \begin{bmatrix}15 \\ 18 \\ 18\end{bmatrix}$ > Bases : > $$ > \left\{\begin{bmatrix}1 \\ 0\end{bmatrix}, \begin{bmatrix}2 \\ 1\end{bmatrix}\right\} > $$ > $$ > \left\{\begin{bmatrix}-3 \\ -2 \\ -2\end{bmatrix}, \begin{bmatrix}1 \\ 0 \\ 0\end{bmatrix}, \begin{bmatrix}0 \\ 1 \\ 0\end{bmatrix}\right\} > $$ >```tikz >\usepackage{tikz-3dplot} >\tdplotsetmaincoords{70}{110} > \begin{document} > \begin{tikzpicture}[scale = .5, cap = round] > \draw[->] (-1, 0) -- (5, 0) node[left] {$x_1$}; > \draw[->] (0, -1) -- (0, 5) node[right] {$x_2$}; > \draw[orange, ->, style = very thick] (0, 0) -> (-2.5, 0) node[left] {$-5 \cdot (1, 0)$}; > \draw[orange, ->, style = very thick] (-2.5, 0) -> (3, 4) node[midway, above] {$4 \cdot (2, 1) \qquad$}; > \draw[red, ->, style = very thick] (0, 0) -> (1, 0) node[right] {(1, 0)}; > \draw[red, ->, style = very thick] (0, 0) -> (2, 1) node[right] {$(2, 1)$}; > \draw[teal, ->, style = very thick] (0, 0) -> (3, 4) node[right] {$(3, 4)$}; > \end{tikzpicture} > \begin{tikzpicture}[scale=1,tdplot_main_coords] > \draw[->] (-2, 0, 0) -- (2, 0, 0) node[right] {$y_1$}; > \draw[->] (0, -2, 0) -- (0, 2, 0) node[right] {$y_2$}; > \draw[->] (0, 0, -2) -- (0, 0, 2) node[right] {$y_3$}; > > \draw[orange, ->, style = very thick] (0, 0) -> (-3, -2, -2) node[left] {$(-3, -2, -2)$}; > \draw[teal, ->, style = very thick] (0, 0) -> (6, 4, 4) node[right] {$-5 \cdot (-3, -2, -2)$}; > \draw[red, ->, style = very thick] (0, 0) -> (1, -1, 2) node[left] {$(1, -1, 2)$}; > \end{tikzpicture} > \end{document} > ``` > This is quite fascinating, as it like taking the original system, and changing the basis by $\begin{bmatrix}-3 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & -1\end{bmatrix}$, or just imaging scaling each vector component of the original basis vector in $\R^3$ by the values above! > One thing to observe is that this new system does not have the same span as the original, and therefore, the basis vector of the span is not the same as the original question! But there is one thing that is really important, the two have the same solution space! A couple of observations from this problem alone! 1) If we have a $T : V \to W$ and $dimV < dim W$, then $kerT \neq \{0\}$, but if it is, then $ketT = \{0\}$
11 coins
scale, 10 coins same, 1 coin different(could be heavier or lighter)
method 1, binary search
5 and 5 coins,
- if equal, then outlier is
- else, take 1 pile, and do the same operation 2 and 2 coins 1 and 1 coin
- Problem, we need to know at the start whether or not the coin weighs more or less, because at step 2, we may choose the wrong pile!
Method 2 Case 1: Coin is heavier
- coin is heavier
- 4 and 4
- Choose lighter 4, they are equal, then that means the coin is heavier
Method 3 3 v 3 different
- then take one pile 50%, if sm 3 v 3 all equal
take one from the equal pile,
Method 4: 2 vs 2:
- different 2 v 2 1 v 1
- You still need a 4th step
7 weigh the same