Week 00-2: Linear Equations

This page is under construction

Linear Equations

Covers Practice Set 0, questions 1-3

A linear equation is an equation where each variable has a degree of 1. Here are a couple examples of both linear and nonlinear equations:

Linear Equation	Nonlinear Equation
$$4x+5y=6$$	$$x^2+y^2=4$$
$$8x=6y$$	$$y*y=5$$

Linear Functions

To get a formal intuition of linear equations, we must cover what a linear function is. Linear functions are special in that if we scale the input to our function by some factor, the output of the function will be evenly scaled.

To put this in fancy formal terms, we can define a linear function as a function $f$ of one scalar argument with the property that for arbitrary scalars $\alpha$ and $x$, $$f(\alpha x) = \alpha * f(x)$$

In other words, if the input to a linear function is multiplied by a scalar $\alpha$, the output will be multiplied by $\alpha$ as well.

We can get a more generic proof that demonstrates that any function with a single scalar input and output can be written in the form $f(x)=kx$ for some constant $k$.

Let $f(x)$ be an arbitrary linear function. By the definition of linear functions, $$f(x) = f(x * 1) = x * f(1).$$

In this case, $f(1)$ is our scalar constant, as it does not depend on $x$. If we let $k = f(1)$, we have shown that there exists a $k$ such that $$f(x) = kx,$$

regardless of what we choose $f(x)$ to be, as long as it is a linear function.

Affine Functions

That is great and all, but why is $f_1(x)=2x+3$ is not a linear function? It looks like a line to me! However, when we look at the function itself, we notice that it doesn’t quite match up with our linear form: $$\underbrace{f_1(x) = 2x}_{f(x) = kx} \boxed{+ 3}$$

We have a constant added to our function! So, is it still linear? Let’s plug in some values to find out.

Choosing $x = 1$ and $x = 2$, we see that $$f_1(1) = 5 \text{ and } f_1(2) = 7,$$

so doubling our input increases the output by a factor of $7/5$! For this reason, this function is not linear even though it still behaves like a line on a graph.

The key observation to make here is that we have the sum of a linear function of $x$ added to a scalar constant. We call functions with this kind of behavior affine functions. Although $f_1(x)$ is not linear, we can say that it is affine.

Because we can express any linear function as being the sum of itself and a scalar constant of 0, all linear functions are also affine, but not all affine functions are linear.

Affine functions tend to commonly be confused with linear functions since they both describe a line on a graph. However, this kind of classification is incorrect. Just remember, affine functions are not linear functions!

Linear Equations (for real this time)

Now that we know what both linear and affine functions are, we are ready to approach linear equations!

A linear equation is equation where each side is a sum of scalar-valued linear functions of each of the unknowns plus a constant.

We will deepen our understanding of linear equations with the following definition:

Formal-ish Definition of a Linear Equation

Consider $f(x_1, x_2, \mathellipsis, x_N) : \reals^n \rightarrow \reals$.

$f$ is linear if the following identity holds:

Homogeneity
- $f(ax_1, \mathellipsis, ax_N) = af(x_1, \mathellipsis, x_N)$
- (if you multiply all inputs to $f$ by $a$, it is the same thing as multiplying the function $f$ itself by $a$)
Super Position
- if $x_i = y_i + z_i$, then $f(y_1+z_1, \mathellipsis, y_N + z_N) = f(y_1, \mathellipsis, y_N)+ f(z_1, \mathellipsis, z_N)$

All of this is a fancy way to say that we can always express a linear equation as $$ f(x_1, x_2, \mathellipsis, x_N) = c_1x_1 + c_2x_2 + \mathellipsis + c_Nx_N $$

Vectors and Matrices

Now, we will go over some new ways to represent systems of linear equations, helping us deal with them in a more compact form.

Vectors

A vector is an ordered list of numbers. Say we are given a collection of $n$ real numbers : $x_1, x_2, \mathellipsis, x_N$. We can represent this as:

$$ \vec{x} = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_N \end{bmatrix} $$

Matrices

A matrix is a rectangular array of numbers, written as:

$$ \vec{A} = \begin{bmatrix} A_{11} & \dots & A_{1n} \\ \vdots & \ddots & \vdots \\ A_{m1} & \dots & A_{mn} \end{bmatrix} $$

Each $A_{ij}$ is a component, or element of the matrix $A$, where $i$ represents the row, and $j$ represents the column.

Representing a Linear System as a Matrix

Consider the set of $M$ linear equations with $N$ variables:

$$ a_{11}x_1 + a_{12}x_2 + \dots + a_{1N}x_N = b_1 \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2N}x_N = b_2 \\ \vdots \\ a_{M1}x_1 + a_{M2}x_2 + \dots + a_{MN}x_N = b_M $$

We can write this in a compact way using an augmented matrix using only the coefficients:

$$ \left[\hspace{-5pt}\begin{array}{cccc|c} a_{11} & a_{12} & \dots & a_{1N} & b_1 \\ a_{21} & a_{22} & \dots & a_{2N} & b_2 \\ \vdots & & \vdots & & \vdots \\ a_{M1} & a_{M2} & \dots & a_{MN} & b_M \end{array}\hspace{-5pt}\right] $$