hehehe

formal system

a formal system describes a formal language for…

1. writing finite mathematical statements
2. have a definition of what statements are true
3. has a definition of a proof of a statement

examples

Every Turing Machine \(M\) defines some formal system \(\mathcal{F}\) such that \(\Sigma^{*}\) string \(w\) represents the statement “\(M\) accepts \(w\)”

• “true statements \(\mathcal{F}\)” is \(L(M)\)
• a proof that \(M\) accepts \(w\) can be defined to be an accepting computation history on \(M\) for \(w\)

interesting

a formal system \(\mathcal{F}\) is “interesting” if:

matricies are like buckets of numbers. ok, ok, seriously:

matricies are a way of encoding the basis of domain proof: that if Linear Maps are determined uniquely by where they map the basis anyways, why don’t we just make a mathematical object that represents that to encode the linear maps.

definition

Let \(n\), \(m\) be positive integer. An \(m\) by \(n\) matrix \(A\) is a rectangular array of elements of \(\mathbb{F}\) with \(m\) rows and \(n\) columns:

If we have some system:

\begin{equation} x’ = Ax \end{equation}

the solution for this system should be \(e^{At}\). This gives rise to, given the power series:

\begin{equation} e^{At} = 1 + At + \frac{1}{2} \qty(At)^{2} + \frac{1}{3!} (At)^{3}+ \dots \end{equation}

the derivative of which:

\begin{align} \dv t e^{At} &= A + A^{2}t + \frac{A^{3}t^{2}}{2} + \dots \\ &= A\qty(1 + At + \frac{A^{2}t^{2}}{2}) \end{align}

This intuition makes sense for all matrices \(A\). Meaning the general solution gives:

matrix multiplication is defined such that the expression \(\mathcal{M}(ST) = \mathcal{M}(S)\mathcal{M}(T)\) holds:

\begin{equation} (AC)_{j,k} = \sum_{r=1}^{n}A_{j,r}C_{r,k} \end{equation}

While matrix multiplication is distributive and associative, it is NOT!!!!!!!!!!! commutative. I hope you can see that \(ST\neq TS\).

memorization

• its always row-by-column, move down rows first then columns
• multiply element-wise and add (row times column and add)

other ways of thinking about matrix multiplication

• it is “row times column”: \((AC)_{j,k} = A_{j, .} \cdot C_{., k}\)
• it is “matrix times columns”: \((AC)_{. , k} = A C_{., k}\)

matrix as a linear combinator

Suppose \(A\) is an \(m\) by \(n\) matrix; and \(c = \mqty(c_1\\ \vdots\\ c_{0})\) is an \(n\) by \(1\) matrix; then: