MTH 215 — Intro to Linear Algebra

Homework 4

Due Friday, April 10 at 11:59pm

Your work must follow the homework policies and submission guidelines in the Syllabus and on Brightspace.

Both sections (in their respective formats and locations described above) are due:

Friday, April 10 at 11:59pm
Late work will not be considered!

1. Consider the subsets of $\R^2$. The bold boundary lines are included in the set, and the sets are assumed to continue “off the graph”. For example, the first region goes infinitely up and infinitely to the right.

   All regions below are NOT subspaces in $\R^2$. Why not? Identify (and justify) which of the three defining properties fail and which, if any, pass. Observe that it may not be the case that all three properties fail!

   
   
   
   

2. Consider the matrix $A$ and the corresponding reduced row echelon form: \[ A = \mat{rrrrr} 1 & 2 & 1 & 1 & 5 \\ -2 & -4 & 0 & 4 & -2 \\ 1 & 2 & 2 & 4 & 9 \rix \qquad\qquad \text{rref } = \mat{rrrrr} 1 & 2 & 0 & -2 & 1 \\ 0 & 0 & 1 & 3 & 4 \\ 0 & 0 & 0 & 0 & 0 \rix .\] Find bases for the following subspaces: $\Col (A)$, $\Null (A)$, $\Row(A)$. State their dimensions.

3. Suppose $A$ is a $3\times 3$ matrix such that \[ \Col (A) \eq \Span \cbr{\mat{r} 1 \\ 2 \\ 3 \rix, \mat{r} 1 \\ -1 \\ 2 \rix}, \qquad \Null (A) = \Span \cbr{\mat{r} -2 \\ 1 \\ 0 \rix} .\]

   1. Let $\vec{b} = \mat{r} 1 \\ -7 \\ 0 \rix$. Is $A \vec{x} = \vec{b}$ consistent?
   2. Is the solution to $A \vec{x} = \vec{b}$ unique? Why or why not? Justify your answer and show all necessary work.

4. Recall that $\cP_n$ denotes the set of polynomials of degree at most $n$. Define a transformation $D$ on $\cP_3$ that maps \[ p(t) = a_3 t^3 + a_2 t^2 + a_1t + a_0 \qquad \text{to} \qquad 3a_3 t^2 + 2a_2 t + a_1 .\] Notice that a general term $a_k t^k$ is mapped to $k a_k t^{k-1}$. This transformation $D$ is called the derivative transformation, and is used in calculus. Knowing calculus is not required for what follows.

   1. What is the domain and codomain of $D$?
   2. Describe the “null space” of the transformation $D$. That is, describe all polynomials which get mapped to the zero polynomial. Your answer will be a set of certain polynomials. Show all necessary work.
   3. It turns out that $D$ is a linear transformation. Certainly you know this if you've taken calculus. Consider it to be given information.

      When provided a polynomial $p(t) = a_3 t^3 + a_2 t^2 + a_1t + a_0$ in $\cP_3$, suppose you write the coefficients in a $4\times 1$ vector $\vec{x} = (a_3, a_2, a_1, a_0)^T$ (shown as a row vector for sake of space). Determine a $3\times 4$ matrix $A$ such that $A \vec{x}$ gives the analogous vector for the image of $p$ under $D$.

   4. Explain why your answer to part (c) justifies your answer to part (b). As a hint, think about the nullspace of the matrix $A$.

5. Lights Out is an electronic game released in 1995. It consists of a $5\times 5$ grid of lights that are either on or off. When the game starts, some lights are turned on randomly. Pressing a light turns it on, if it was previously off, or turns it off, if it was previously on. In either case, whenever a light is pressed, all perpendicularly adjacent lights toggle their state.

   Let's see a simple example. Here, white squares denote “off” and gray squares denote “on”.

   The goal of the game is to turn off all the lights (hence its name) with the fewest number of presses.

   To model the game, we will use the number system $\Z_2 = \cbr{0,1}$ where $0$ represents the off state and $1$ the on state. Alternatively, $1$ represents the act of pressing a square and $0$ represents doing nothing. That is,

   • $0 + 0 = 0$ (not pressing an off square leaves it off)
   • $0 + 1 = 1$ (pressing an off square turns it on)
   • $1 + 0 = 1$ (not pressing a lit square leaves it lit)
   • $1 + 1 = 0$ (pressing a lit square turns it off)

   Some of you may recognize this as addition modulo $2$. That is, we are adding the numbers and taking the remainder (the modulus) when divided by $2$. For example, $0+0=0$ because $0 \div 2$ has a remainder of $0$, meanwhile $1+1=0$ because $(1+1) \div 2$ has a remainder $0$.

   Going forward, any vectors and matrices will be taken from $\Z_2 = \cbr{0,1}$ and calculations are done in $\Z_2$.

   While we could view the game as a $5\times 5$ matrix, it is better to “unravel” it as a $25\times 1$ column vector, numbering the squares from 1 to 25 row by row.

   1	2	3	4	5
   6	7	8	9	10
   11	12	13	14	15
   16	17	18	19	20
   21	22	23	24	25

   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25

   Just as $\R^{25}$ is a vector space, it turns out that $\Z_2^{25}$ is a vector space as well but with addition and multiplication done modulo $2$.

   To press square $i$, we add a vector $\vec{m}_i$ to the current configuration. This vector has $1$'s in position $i$ and in all positions corresponding to squares adjacent to $i$, and $0$ elsewhere. For example, pressing square 1 (top-left) affects squares 1, 2, and 6: \[ \vec{m}_1 = \mat{*{25}c} 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \rix^T .\]

   Doing this for all 25 squares gives the matrix $M$, where blank entries denote $0$'s and $M = \mat{ccc} \vec{m}_1 & \dots & \vec{m}_{25} \rix$ is a $25 \times 25$ matrix.

   \[ M = \mat{ccc} \vec{m}_1 & \dots & \vec{m}_{25} \rix = \mat{*{5}c|*{5}c|*{5}c|*{5}c|*{5}c} 1 & 1 & & & & 1 & & & & & & & & & & & & & & & & & & & \\ 1 & 1 & 1 & & & & 1 & & & & & & & & & & & & & & & & & & \\ & 1 & 1 & 1 & & & & 1 & & & & & & & & & & & & & & & & & \\ & & 1 & 1 & 1 & & & & 1 & & & & & & & & & & & & & & & & \\ & & & 1 & 1 & & & & & 1 & & & & & & & & & & & & & & & \\\hline 1 & & & & & 1 & 1 & & & & 1 & & & & & & & & & & & & & & \\ & 1 & & & & 1 & 1 & 1 & & & & 1 & & & & & & & & & & & & & \\ & & 1 & & & & 1 & 1 & 1 & & & & 1 & & & & & & & & & & & & \\ & & & 1 & & & & 1 & 1 & 1 & & & & 1 & & & & & & & & & & & \\ & & & & 1 & & & & 1 & 1 & & & & & 1 & & & & & & & & & & \\\hline & & & & & 1 & & & & & 1 & 1 & & & & 1 & & & & & & & & & \\ & & & & & & 1 & & & & 1 & 1 & 1 & & & & 1 & & & & & & & & \\ & & & & & & & 1 & & & & 1 & 1 & 1 & & & & 1 & & & & & & & \\ & & & & & & & & 1 & & & & 1 & 1 & 1 & & & & 1 & & & & & & \\ & & & & & & & & & 1 & & & & 1 & 1 & & & & & 1 & & & & & \\\hline & & & & & & & & & & 1 & & & & & 1 & 1 & & & & 1 & & & & \\ & & & & & & & & & & & 1 & & & & 1 & 1 & 1 & & & & 1 & & & \\ & & & & & & & & & & & & 1 & & & & 1 & 1 & 1 & & & & 1 & & \\ & & & & & & & & & & & & & 1 & & & & 1 & 1 & 1 & & & & 1 & \\ & & & & & & & & & & & & & & 1 & & & & 1 & 1 & & & & & 1 \\\hline & & & & & & & & & & & & & & & 1 & & & & & 1 & 1 & & & \\ & & & & & & & & & & & & & & & & 1 & & & & 1 & 1 & 1 & & \\ & & & & & & & & & & & & & & & & & 1 & & & & 1 & 1 & 1 & \\ & & & & & & & & & & & & & & & & & & 1 & & & & 1 & 1 & 1 \\ & & & & & & & & & & & & & & & & & & & 1 & & & & 1 & 1 \\ \rix \]

   Suppose the game starts with a $25\times 1$ initial vector $\vec{c}$ in $\Z_2^{25}$, called the initial configuration. That is, $\vec{c}$ was randomly chosen (say) by the computer and each component is either $0$ (if the light is off) or $1$ (if the light is on).

   If the user wants to press the $i$-th square, then the new configuration is $\vec{c}_1 = \vec{m}_i + \vec{c}$.

   1. What happens if the user presses the $i$-th square twice in a row? Explain this using knowledge of how modular addition works in $\Z_2$.
   2. Is pressing square $i$ and then pressing square $j$ equivalent to pressing square $j$ and then square $i$? That is, does the order in which two squares are pressed matter? Be specific with your answer (and perhaps cite properties of vector spaces).
   3. Parts (a) and (b) motivate critically important observations. Explain why the following statements are true. Be specific!
      • If a square needs to be pressed at all, it suffices to press it only once.
      • If certain squares need to be pressed, the order of doing so does not matter.
   4. The previous questions show that we need to determine which squares to press. Let $x_i=1$ if we need to press square $i$, and $x_i=0$ if we don't. Then we need to solve \[ x_1 \vec{m}_1 + x_2 \vec{m}_2 + \dots + x_{25} \vec{m}_{25} + \vec{c} \eq \vec{0} .\] Explain why solving this equation is equivalent to solving the equation \[ x_1 \vec{m}_1 + x_2 \vec{m}_2 + \dots + x_{25} \vec{m}_{25} \eq \vec{c} \] and then explain why this is equivalent to solving \[ M \vec{x} \eq \vec{c} .\]
   5. To solve a Lights Out game, we need to find a solution (if it exists) to $M \vec{x} = \vec{c}$. The RREF of the $25\times 25$ matrix $M$ is below. Blank entries denote $0$'s, and divider lines are placed every 5 rows and columns. \[ \text{rref} (M) = \mat{*{5}c|*{5}c|*{5}c|*{5}c|*{5}c} 1 & & & & & & & & & & & & & & & & & & & & & & & 0 & 1 \\ & 1 & & & & & & & & & & & & & & & & & & & & & & 1 & 0 \\ & & 1 & & & & & & & & & & & & & & & & & & & & & 1 & 1 \\ & & & 1 & & & & & & & & & & & & & & & & & & & & 1 & 0\\ & & & & 1 & & & & & & & & & & & & & & & & & & & 0 & 1 \\\hline & & & & & 1 & & & & & & & & & & & & & & & & & & 1 & 1 \\ & & & & & & 1 & & & & & & & & & & & & & & & & & 0 & 0 \\ & & & & & & & 1 & & & & & & & & & & & & & & & & 1 & 1 \\ & & & & & & & & 1 & & & & & & & & & & & & & & & 0 & 0\\ & & & & & & & & & 1 & & & & & & & & & & & & & & 1 & 1 \\\hline & & & & & & & & & & 1 & & & & & & & & & & & & & 1 & 0 \\ & & & & & & & & & & & 1 & & & & & & & & & & & & 1 & 0 \\ & & & & & & & & & & & & 1 & & & & & & & & & & & 0 & 0 \\ & & & & & & & & & & & & & 1 & & & & & & & & & & 1 & 0 \\ & & & & & & & & & & & & & & 1 & & & & & & & & & 1 & 0 \\\hline & & & & & & & & & & & & & & & 1 & & & & & & & & 1 & 1 \\ & & & & & & & & & & & & & & & & 1 & & & & & & & 0 & 0 \\ & & & & & & & & & & & & & & & & & 1 & & & & & & 1 & 1 \\ & & & & & & & & & & & & & & & & & & 1 & & & & & 0 & 0 \\ & & & & & & & & & & & & & & & & & & & 1 & & & & 1 & 1 \\\hline & & & & & & & & & & & & & & & & & & & & 1 & & & 0 & 1 \\ & & & & & & & & & & & & & & & & & & & & & 1 & & 1 & 0 \\ & & & & & & & & & & & & & & & & & & & & & & 1 & 1 & 1 \\ & & & & & & & & & & & & & & & & & & & & & & & 0 & 0\\ & & & & & & & & & & & & & & & & & & & & & & & 0 & 0 \rix .\] Using the RREF of $M$, determine a basis for the column space of $M$. Please do not write the full vectors out! Answers such as $\cbr{\vec{m}_i \:\mid\: 1\le i\le 10, \, i=15, \, 18}$ are acceptable.
   6. Using the RREF of $M$ above, explain in words why not every Lights Out game can be solved. Your answer should indicate what needs to happen in order for games to be solvable.
   7. A basis for $\Null(M)$ is $\cbr{\vec{u}_1, \vec{u}_2}$ where \begin{align*} \vec{u}_1 & \eq \mat{*{25}c} 0 & 1 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 \rix^T \\ \vec{u}_2 & \eq \mat{*{25}c} 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \rix^T. \end{align*}

      In order to go further, we need to take a brief aside and explain orthogonal vectors.

      If you don't understand everything below, that is okay. You can skip to the punchline below.

      Definition: Two $n\times 1$ vectors $\vec{x}$ and $\vec{y}$ in a vector space are orthogonal (also called perpendicular) if the following equation holds: \[ x_1 y_1 + x_2 y_2 + \dots + x_n y_n \eq \vec{x}^T \vec{y} \eq 0 .\] The sum on the left-hand side is called the inner product or dot product, denoted by $\vec{x} \bullet \vec{y}$.

      That is, two vectors are orthogonal if and only if their inner product is zero.

      For example, in $\R^2$, vectors $\vec{x} = \mat{r} 1 \\ 2 \rix$ and $\vec{y} = \mat{r} 2 \\ -1\rix$ are orthogonal since $x_1 y_1 + x_2 y_2 = 1(2) + 2(-1) = 0$. In $\R^2$, orthogonal vectors are at a right angle to each other.

      Notice that by definition of the matrix-vector product, $\vec{x}^T \vec{y}$ is exactly the sum in the definition above. And, that this product is $1\times 1$ (i.e., a scalar).

      We will cover orthogonal vectors and such in Chapter 6.

      We might see how orthogonality is going to come into the picture. First, we need a result.

      Theorem: Let $A$ be an $n\times n$ matrix. If $\vec{x}$ is any vector in $\Col (A)$ and $\vec{y}$ is any vector in $\Null (A^T)$, then $\vec{x}$ and $\vec{y}$ are orthogonal (so $\vec{x} \bullet \vec{y} = 0$).

      Now, let's go back to the task at hand.

      Suppose $\vec{c} = \mat{ccc} c_1 & \dots & c_{25} \rix^T$ is an initial configuration that is solvable. Then $\vec{c}$ must be in $\Col (M)$ and, by the Theorem, $\vec{c}$ is orthogonal to the two null space basis vectors $\vec{u}_1, \, \vec{u}_2$ above. Recall that $M$ is symmetric, meaning $M= M^T$, and so $\Null (M) = \Null (M^T)$.

      Computing $\vec{c} \bullet \vec{u}_1$ and $\vec{c} \bullet \vec{u}_2$ and setting to $0$ gives, respectively, \begin{align*} 0 &= c_2 + c_3 + c_4 + c_6 + c_8 + c_{10} + c_{11} + c_{12} + c_{14} + c_{15} + c_{16} + c_{18} + c_{20} + c_{22} + c_{23} + c_{24} \\ 0 &= c_1 + c_3 + c_5 + c_6 + c_8 + c_{10} + c_{16} + c_{18} + c_{20} + c_{21} + c_{23} + c_{25} \end{align*}

      Key: If an initial configuration $\vec{c}$ does not satisfy these two equations, the game is not solvable.

   8. A solvable configuration is \[ \vec{c} = \mat{*{5}c|*{5}c|*{5}c|*{5}c|*{5}c} 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 1 & 1 \rix^T .\] Below is the rref for the augmented matrix $\mat{c||c} M & \vec{c} \rix$. Blank entries denote zeros, and the double bar signifies the augmented vector (the single divider lines are for readability).

      \[ \text{rref of } \mat{c||c} M & \vec{c} \rix = \mat{*{5}c|*{5}c|*{5}c|*{5}c|*{5}c||c} 1 & & & & & & & & & & & & & & & & & & & & & & & 0 & 1 & 0 \\ & 1 & & & & & & & & & & & & & & & & & & & & & & 1 & 0 & 0 \\ & & 1 & & & & & & & & & & & & & & & & & & & & & 1 & 1 & 1 \\ & & & 1 & & & & & & & & & & & & & & & & & & & & 1 & 0 & 1 \\ & & & & 1 & & & & & & & & & & & & & & & & & & & 0 & 1 & 1 \\\hline & & & & & 1 & & & & & & & & & & & & & & & & & & 1 & 1 & 0 \\ & & & & & & 1 & & & & & & & & & & & & & & & & & 0 & 0 & 1 \\ & & & & & & & 1 & & & & & & & & & & & & & & & & 1 & 1 & 0 \\ & & & & & & & & 1 & & & & & & & & & & & & & & & 0 & 0 & 1 \\ & & & & & & & & & 1 & & & & & & & & & & & & & & 1 & 1 & 1 \\\hline & & & & & & & & & & 1 & & & & & & & & & & & & & 1 & 0 & 0 \\ & & & & & & & & & & & 1 & & & & & & & & & & & & 1 & 0 & 1 \\ & & & & & & & & & & & & 1 & & & & & & & & & & & 0 & 0 & 0 \\ & & & & & & & & & & & & & 1 & & & & & & & & & & 1 & 0 & 0 \\ & & & & & & & & & & & & & & 1 & & & & & & & & & 1 & 0 & 0 \\\hline & & & & & & & & & & & & & & & 1 & & & & & & & & 1 & 1 & 0 \\ & & & & & & & & & & & & & & & & 1 & & & & & & & 0 & 0 & 0 \\ & & & & & & & & & & & & & & & & & 1 & & & & & & 1 & 1 & 0 \\ & & & & & & & & & & & & & & & & & & 1 & & & & & 0 & 0 & 0 \\ & & & & & & & & & & & & & & & & & & & 1 & & & & 1 & 1 & 1 \\\hline & & & & & & & & & & & & & & & & & & & & 1 & & & 0 & 1 & 1 \\ & & & & & & & & & & & & & & & & & & & & & 1 & & 1 & 0 & 1 \\ & & & & & & & & & & & & & & & & & & & & & & 1 & 1 & 1 & 1 \\ & & & & & & & & & & & & & & & & & & & & & & & 0 & 0 & 0 \\ & & & & & & & & & & & & & & & & & & & & & & & 0 & 0 & 0 \rix \]

      Your Task: Determine a solution $\vec{x} = (x_1, \dots , x_{25})$ to $M \vec{x} = \vec{c}$ when the free variables are $0$.

   9. Optional: No work required. Given the initial configuration in part (h), try solving the game! To create the game with initial configuration shown above, use the following Geogebra file: https://www.geogebra.org/m/wcmctahp
      • Click the button “Click to Design” to create a custom game. Here, yellow means “1” (on) and black means “0” (off).
      • Once you are done, click the button “Click to Play”.
      • Hit the squares as your solution $\vec{x}$ dictates. Recall that when $x_k = 1$ you press the $k$-th square and when $x_k=0$ you do nothing.
      • If your solution is correct (and if you correctly set up the game), all squares should be black.

      You don't have to submit any work for this part. Have fun!

   10. In the MATLAB file on Brightspace is a setup for you to create your own Lights Out game. No coding is required! Upon execution, a RREF of $\mat{c|c} M & \vec{c} \rix$ is generated where $\vec{c}$ is a solvable configuration.

       From the RREF, determine a solution similar to how we did before. You can choose any values for the free variables (both 0, both 1, or mix-match).

       Your Task: Look at your initial configuration vector $\vec{c}$. In the grid below, shade the squares that are assigned initially to “on”. Then, write the sequence of squares that need to be pressed in order to solve the game. For full credit, I should be able to solve your game with your steps listed!

       1	2	3	4	5
       6	7	8	9	10
       11	12	13	14	15
       16	17	18	19	20
       21	22	23	24	25

       NOTE 1: You do NOT have to submit any MATLAB files for this entire question.

       NOTE 2: You need to enter your URI student ID number in the corresponding rng( ) location in the template file on Brightspace (so you don't all have the same game). The template file MUST be used!