Linear Equations over Different Fields

Linear Equations on different Fields?

In this post, we will explore how solutions to a system of linear equations differ over different fields. If we are given a system of linear equations, how do we determine it has solution? And if it does, will its solution change over different fields?

For example, if I have three linear equations that have a unique solution in $\mathbb{Z}/p\mathbb{Z}$, will this same system have a unique solution in $\mathbb{Q}$, $\mathbb{R}$, or even $\mathbb{C}$? Well, with some clever abstract algebra and some help with linear algebra, we can explore this question with the following proof:

Question

Three Simultaneous equations over any field $F$

Prove the three simultaneous equations

$$\begin{array}{r}ax+by+cz=d,a^{\prime }x+b^{\prime }y+c^{\prime }z=d^{\prime },a^{\prime \prime }x+b^{\prime \prime }y+c^{\prime \prime }z=d^{\prime \prime }\end{array}$$

have one and only one solution in any field $F$ if the $3\times 3$ determinant

$$\begin{array}{r}\Delta =a{b}^{\prime }{c}^{\prime \prime }+a^{\prime }{b}^{\prime \prime }c+a^{\prime \prime }b{c}^{\prime }-a^{\prime \prime }{b}^{\prime }c-a^{\prime }b{c}^{\prime \prime }-a{b}^{\prime \prime }{c}^{\prime }\ne 0\end{array}$$

Proof

Suppose the 3x3 deteminant is non-zero but we also have two solutions to the equation denoted as $(x_1,y_1,z_1)$ and $(x_2,y_2,z_2)$, then

$$\begin{array}{rl}a{x}_1+b{y}_1+c{z}_1& =d\\ a{x}_2+b{y}_2+c{z}_2& =d\\ a^{\prime }{x}_1+b^{\prime }{y}_1+c^{\prime }{z}_1& =d^{\prime }\\ a^{\prime }{x}_2+b^{\prime }{y}_2+c^{\prime }{z}_2& =d^{\prime }\\ a^{\prime \prime }{x}_1+b^{\prime \prime }{y}_1+c^{\prime \prime }{z}_1& =d^{\prime \prime }\\ a^{\prime \prime }{x}_2+b^{\prime \prime }{y}_2+c^{\prime \prime }{z}_2& =d^{\prime \prime }\end{array}$$

Then we can rewrite this system as

$$\begin{array}{rl}a(x_1-x_2)+b(y_1-y_2)+c(z_1-z_2)& =0\\ a^{\prime }(x_1-x_2)+b^{\prime }(y_1-y_2)+c^{\prime }(z_1-z_2)& =0\\ a^{\prime \prime }(x_1-x_2)+b^{\prime \prime }(y_1-y_2)+c^{\prime \prime }(z_1-z_2)& =0\end{array}$$

Since $x_1,x_2,y_1,y_2,z_1,z_2\in F$, then $(x_1-x_2),(y_1-y_2),(z_1-z_2)\in F$. Lets denote them as followed, $\alpha =(x_1-x_2),\beta =(y_1-y_2),\gamma =(z_1-z_2)$. Therefore our system will look like:

$$\begin{array}{rl}a\cdot \alpha +b\cdot \beta +c\cdot \gamma & =0\\ a^{\prime }\cdot \alpha +b^{\prime }\cdot \beta +c^{\prime }\cdot \gamma & =0\\ a^{\prime \prime }\cdot \alpha +b^{\prime \prime }\cdot \beta +c^{\prime \prime }\cdot \gamma & =0\end{array}$$

Since F is a field, then if the coefficients of $\alpha ,\beta ,\gamma$ = 0, then we can trivialy see that we reduce the equation even futher, making the system smaller. Now if we assume that the coefficients are non-zero, we use Guassian Ellimination by multiplying both sides of the equation by their inverses, and eventually we will arrive with a system where

$$\begin{array}{r}\left[\begin{array}{cccc}\alpha & & & 0\\ & \beta & & 0\\ & & \gamma & 0\end{array}\right]\end{array}$$

then that means $0=(x_1-x_2),0=(y_1-y_2),0=(z_1-z_2)\Rightarrow x_1=x_2,y_1=y_2,z_1=z_2$. Therefore, if the determinant of the matrix is non-zero, then there must exists only one solution.

Another approach is using linear algebra techniques to reach the same conclusion as a matrix with a non-zero determinant means that the matrix is invertible!, therefore we can express

$$\begin{array}{r}\left[\begin{array}{ccc}a& b& c\\ a^{\prime }& b^{\prime }& c^{\prime }\\ a^{\prime \prime }& b^{\prime \prime }& c^{\prime \prime }\end{array}\right]\left[\begin{array}{c}\alpha \\ \beta \\ \gamma \end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]\end{array}$$

Hence,

$$\begin{array}{r}\left[\begin{array}{c}\alpha \\ \beta \\ \gamma \end{array}\right]={\left[\begin{array}{ccc}a& b& c\\ a^{\prime }& b^{\prime }& c^{\prime }\\ a^{\prime \prime }& b^{\prime \prime }& c^{\prime \prime }\end{array}\right]}^{-1}\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]\Rightarrow \alpha =0,\beta =0,\gamma =0\end{array}$$

Some Worked Examples

Does this work with systems of only 2 equations?

Let us examine the following equations over two different fields:

$$\begin{array}{rl}\begin{array}{c}4x+6y=10\\ x-y=4\end{array}& \begin{array}{c}4x+6y\equiv 10(\mathrm{mod}3)\\ x-y\equiv 4(\mathrm{mod}3)\end{array}\\ & \\ & \\ \Delta & =\left|\begin{array}{cc}4& 6\\ 1& -1\end{array}\right|=-10\end{array}$$

In $\mathbb{R}$, our solution for (x, y) = (17/5, -3/5), while in $\mathbb{Z}/3\mathbb{Z}$, (x, y) = (1, 0). I want you to closely observe how the solutions are quite different. Even if the coefficients look same, the underlying arithmetic vary as they depend on the field we are using. As a result, we can get drastically different solutions!

3 equations over $\mathbb{Z}/11\mathbb{Z}$

Use the proof to determine $x,y,z$ for the three simultaneous linear equations over $\mathbb{Z}/11\mathbb{Z}$:

$$\begin{array}{rl}3x+5y+7z& \equiv 6(\mathrm{mod}11)\\ 5x+9y+6z& \equiv 7(\mathrm{mod}11)\\ 2x+y+4z& \equiv 3(\mathrm{mod}11)\end{array}$$

Answer

Before we start, lets check if our determinant is non-zero!

$$\begin{array}{rl}\Delta & =3\cdot 9\cdot 4+5\cdot 1\cdot 7+2\cdot 5\cdot 6-2\cdot 9\cdot 7-5\cdot 5\cdot 4-3\cdot 1\cdot 6\\ & =-41\equiv 3(\mathrm{mod}11)\not\equiv 0(\mathrm{mod}11)\end{array}$$

We can quickly find the solutions using Cramer’s rule! Lets examine the coefficient matrix and the variable matrix

$$\begin{array}{r}A=\left[\begin{array}{ccc}a& b& c\\ a^{\prime }& b^{\prime }& c^{\prime }\\ a^{\prime \prime }& b^{\prime \prime }& c^{\prime \prime }\end{array}\right]B=\left[\begin{array}{ccc}d& b& c\\ d^{\prime }& b^{\prime }& c^{\prime }\\ d^{\prime \prime }& b^{\prime \prime }& c^{\prime \prime }\end{array}\right]\end{array}$$

If we compute the determinant of both of these matrices, we get

$$\begin{array}{rl}\Delta =\det (A)& =a{b}^{\prime }{c}^{\prime \prime }+a^{\prime }{b}^{\prime \prime }c+a^{\prime \prime }b{c}^{\prime }-a^{\prime \prime }{b}^{\prime }c-a^{\prime }b{c}^{\prime \prime }-a{b}^{\prime \prime }{c}^{\prime }\\ \det (B)& =d{b}^{\prime }{c}^{\prime \prime }+d^{\prime }{b}^{\prime \prime }c+d^{\prime \prime }b{c}^{\prime }-d^{\prime \prime }{b}^{\prime }c-d^{\prime }b{c}^{\prime \prime }-d{b}^{\prime \prime }{c}^{\prime }\end{array}$$

Expanding the equation in the following way gives us this relation!

$$\begin{array}{r}\Delta x=\det (B)\Rightarrow x={\Delta }^{-1}\det (B)\end{array}$$

So substituting our values, we get:

$$\begin{array}{r}A=\left[\begin{array}{ccc}3& 5& 7\\ 5& 9& 6\\ 2& 1& 4\end{array}\right]B=\left[\begin{array}{ccc}6& 5& 7\\ 7& 9& 6\\ 3& 1& 4\end{array}\right]\end{array}$$ $$\begin{array}{rl}\Delta & \equiv 3(\mathrm{mod}11)\\ {\Delta }^{-1}& \equiv 4(\mathrm{mod}11)\\ \det (B)=-10& \equiv 1(\mathrm{mod}11)\\ x& =4\cdot 1\end{array}$$

To find $y$, we change the second column!

$$\begin{array}{r}C=\left[\begin{array}{ccc}3& 6& 7\\ 5& 7& 6\\ 2& 3& 4\end{array}\right]\end{array}$$ $$\begin{array}{rl}\det (c)=-11& \equiv 0(\mathrm{mod}11)\\ y=4\cdot 0& \equiv 0(\mathrm{mod}11)\end{array}$$

And now for z, we change the third column!

$$\begin{array}{r}D=\left[\begin{array}{ccc}3& 5& 6\\ 5& 9& 7\\ 2& 1& 3\end{array}\right]\end{array}$$ $$\begin{array}{rl}\det (D)=-23& \equiv 10(\mathrm{mod}11)\\ z=4\cdot 10& \equiv 7(\mathrm{mod}11)\end{array}$$

So our unique solution to our system is $(4,0,7)$

Lets do it over $\mathbb{R}$

For the first worked example, we found solutions for the problem in with our field being $\mathbb{Z}/11\mathbb{Z}$. What would happen if we were to do this problem over $\mathbb{R}$? Fortunately, we did most of the busy work, so it’s just plug and play!

$$\begin{array}{rl}3x+5y+7z& =6\\ 5x+9y+6z& =7\\ 2x+y+4z& =3\end{array}$$ $$\begin{array}{r}\Delta =\det (A)=-41\\ \det (B)=-10\\ \det (C)=-11\\ \det (D)=-23\\ x=\frac{10}{41},y=\frac{11}{41},z=\frac{23}{41}\\ (x,y,z)=(\frac{10}{41},\frac{11}{41},\frac{23}{41})\end{array}$$

If we were to graph the three planes, this is what they would look like:

Clearly showing that our proof is right! Since we only have a single point of intersection at $(x,y,z)=(\frac{10}{41},\frac{11}{41},\frac{23}{41})$!

One last question:

What about $\mathbb{Z}/41\mathbb{Z}$

Since 41 is a prime number, $\mathbb{Z}/41\mathbb{Z}$ is a field! But this could pose a problem if our system was posed as such:

$$\begin{array}{rl}3x+5y+7z& \equiv 6(\mathrm{mod}41)\\ 5x+9y+6z& \equiv 7(\mathrm{mod}41)\\ 2x+y+4z& \equiv 3(\mathrm{mod}41)\end{array}$$

Do we even have a solution? Since $\Delta =-41\equiv 0(\mathrm{mod}41)$, we cannot use our proof to ensure us having a single solution. If we were to do a RREF of the Augmented Matrix, we would get the following:

$$\begin{array}{r}\left[\begin{array}{cccc}3& 5& 7& 6\\ 5& 9& 6& 7\\ 2& 1& 4& 3\end{array}\right](\mathrm{mod}41)\to \left[\begin{array}{cccc}1& 0& 37& 30\\ 0& 1& 12& 16\\ 0& 0& 0& 1\end{array}\right](\mathrm{mod}41)\end{array}$$

NO!

Our system has no solution under $\mathbb{Z}/41\mathbb{Z}$! Why? We get a contradiction in the final line where $0x+0y+0z\equiv 1(\mathrm{mod}41)$ which is not possible. While this system may have a single solution in some fields, but they may not have solutions in others!

Inspiration

• (A survey of modern Algebra, Ch 2.3, Q.8, Birkhoff and MacLane)