Problem Set 1: Warm-Up

For each of the following scenarios, provide an example or explain why it is impossible.

1. A system of three linear equations in three variables which has infinitely many solutions, but none of the equations is a scaled copy of another equation (for example, $2x + 4y = 6$ is a scaled copy of $x + 2y = 3$).

   Solution

   There are many solutions. For example, consider

   \[\begin{aligned} x - z & = 0\\ y + z & = 0\\ x + y & = 0. \end{aligned}\]

   Then every point on the line $\{(t,-t,t) : t \in \RR\}$ is a solution of this system of equations.

2. A system of linear equations which has a solution, but after removing an equation from the system, it does not have any solutions.

   Solution

   This is impossible. Each equation in a system of equations imposes an extra constraint, so removing an equation only makes the system easier to solve. That is, removing equations can only add new solutions, not remove existing solutions.

3. Four planes in $\RR^3$ such that any three of the planes intersect in a common point, but the four planes have no common intersection point.

   Solution

   There are many possible answers. For example, consider the planes defined by each of the following four equations

   1. $x = 0$
   2. $y = 0$
   3. $z = 0$
   4. $x + y + z = 1$

   Below we write $(ijk)$ as a shorthand for the intersection of planes $i$, $j$, $k$ and list the intersection point.

   1. $(123)$ contains $(0,0,0)$,
   2. $(124)$ contains $(0,0,1)$,
   3. $(134)$ contains $(0,1,0)$,
   4. $(234)$ contains $(1,0,0)$.

   However, there is no point that belongs to all four planes.

4. A system of two linear equations in three variables for which the solution set is \[ L = \{(2t, t + 1, 3-t) : t \in \RR\}. \]

   Solution

   Suppose $ax + by + cz = d$ is a plane containing $L$. Then that means \[ a(2t) + b(t + 1) + c(3 - t) = d \] holds for all $t \in \RR$. Rearranging this is equivalent to \[ (2a + b - c)t + (b + 3c - d) = 0. \] The only way this can hold for all $t$ is if we have

   \[\begin{aligned} 2a + b - c &= 0\\ b + 3c - d &= 0. \end{aligned}\]

   Solving the first equation for $c$ we get \[ c = 2a + b. \] Solving the second equation for $d$ and substituting our expression for $c$ we get

   If we choose $(a,b) = (1,0), (0,1)$ we then get the pair of planes

   \[\begin{aligned} x + 2z &= 6\\ y + z &= 4. \end{aligned}\]

   These are different planes, hence intersect in at most a line, and by construction they intersect at $L$.

   My problems are too difficult. I think I should scale them back, including this one. Just ask them to find a pair of planes.

5. (Challenge) Four distinct lines in $\RR^2$ such that any three of the lines have a common intersection point, but the four lines have no common intersection point.

   Solution

   This is impossible. Say $\ell_1, \ell_2, \ell_3, \ell_4$ are four lines such that any three intersect at a point. If $\ell_1, \ell_2, \ell_3$ intersect at a point $p$, then the lines $\ell_1, \ell_2$ must already intersect at $p$ and this is the only point where they intersect. But since $\ell_1, \ell_2, \ell_4$ also intersect at a point, that means $p$ also belongs to $\ell_4$, hence $p$ belongs to all four lines.

When presented with a system of equations, the mathematician's first urge is to find the solutions. However, solving equations takes time, effort, and, if there are a lot of equations, it takes money. Sometimes we can learn valuable information about the solutions of an equation without actually solving it. As they say, the fastest (and cheapest) computation is the one you never do.

For systems of linear equations, there are three qualitatively different possibilities for the number of solutions: there will always be either infinitely many, one, or none. In this problem we develop a handy heuristic for determining at a glance which of these qualitative regimes we expect to be in based on the number of variables and the number of equations in our system.

1. Let $n \geq 1$. How we many solutions should we expect a system of $n$ linear equations in two variables to have? Explain why this is the case.

   Solution

   A single equation in two variables describes a line, which has infinitely many points. Hence when $n = 1$ we will always have infinitely many solutions.

   When $n = 2$, the system describes the intersection of two lines, which is typically a single point. Hence in this case there is generally one solution.

   When $n \geq 3$ the system describes the intersection of at least three lines. Generally speaking, three lines will not have a common intersection point. Hence we should expect no solutions.

2. Same question but now with equations in three variables.

   Solution

   With three variables, each linear equation describes a plane. So for $n = 1$, we get a plane of solutions, which is infinite. When $n = 2$, two planes typically intersect in a line, which is infinite. When $n = 3$, we are generally intersecting a line (coming from two of the planes intersection) with a plane, which generally intersects in a single point. When $n \geq 4$, we generally do not expect $n$ planes to intersect, thus we expect no solutions.

3. If you had a system of linear equations in 1000 variables and 850 equations, how many solutions do you expect the system to have and why?

   Solution

   There will be infinitely many solutions. Each of the equations can be used to solve for at most one variable in terms of other variables, so that means we have actual constraints on at most 850 of the variables. Thus there are at least 150 variables with no restrictions at all and these may be chosen freely. Once these free variables are chosen, the rest are determined by the equations. Hence there are infinitely many solutions.

4. Extrapolating from the previous two problems, make a guess about what the answer should for equations in $m \geq 4$ variables.

   Solution

   Extrapolating from the previous two cases, we might expect,

   1. Infinitely many solutions when $m > n$,
   2. One solution when $m = n$, and
   3. No solutions when $m < n$.