Matrices: Definition, Order, and Types

Matrices Definition

• A matrix is a rectangular arrangement of numbers into rows and columns.
• The order of a matrix is defined as (number of rows) x (number of columns).
• Element of matrix A is represented by $a_{ij}$, row number i, and column number j.

Matrix Example

• $A = \begin{bmatrix} 1 & 2 & 3 \ 4 & 5 & 6 \end{bmatrix}_{2 \times 3}$

Types of Matrices

• Row matrix: Has only one row, e.g., $A = \begin{bmatrix} 1 & 5 & 6 \end{bmatrix}_{1 \times 3}$.
• Column matrix: Has only one column, e.g., $A = \begin{bmatrix} 1 \ 5 \ 6 \end{bmatrix}_{3 \times 1}$.
• Square matrix: The number of rows is equal to the number of columns, e.g., $A = \begin{bmatrix} 1 & 2 \ 3 & 4 \end{bmatrix}_{2 \times 2}$.
• Diagonal matrix: A square matrix where all non-diagonal elements are zero, e.g., $A = \begin{bmatrix} 1 & 0 & 0 \ 0 & 5 & 0 \ 0 & 0 & 6 \end{bmatrix}_{3 \times 3}$.
• Scalar matrix: A diagonal matrix with all diagonal elements equal, e.g., $A = \begin{bmatrix} 5 & 0 & 0 \ 0 & 5 & 0 \ 0 & 0 & 5 \end{bmatrix}_{3 \times 3}$.
• Identity or unit matrix: A scalar matrix where all diagonal elements equal 1, e.g., $I = \begin{bmatrix} 1 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & 1 \end{bmatrix}_{3 \times 3}$.
• Null matrix: All elements are zero, e.g., $O = \begin{bmatrix} 0 & 0 \ 0 & 0 \end{bmatrix}_{2 \times 2}$.

Triangular Matrix

• Upper triangular matrix: All elements below the main diagonal are zero, e.g., $A = \begin{bmatrix} 1 & 2 & 3 \ 0 & 5 & 6 \ 0 & 0 & 6 \end{bmatrix}_{3 \times 3}$.
• Lower triangular matrix: All elements above the main diagonal are zero, e.g., $A = \begin{bmatrix} 1 & 0 & 0 \ 4 & 5 & 0 \ 7 & 8 & 6 \end{bmatrix}_{3 \times 3}$.

Transpose of a Matrix

• Achieved by interchanging rows and columns, denoted as, $A^T$ or $A'$

Transpose of a Matrix Properties

• $(A^T)^T = A$
• $(A \pm B)^T = A^T \pm B^T$
• $(KA)^T = KA^T$, where K is a scalar
• $(AB)^T = B^T A^T$

Symmetric Matrix

• A square matrix A is symmetric if $A^T = A$
• Example: $A = \begin{bmatrix} 1 & 2 & 3 \ 2 & 5 & 6 \ 3 & 6 & 9 \end{bmatrix}$

Skew-Symmetric Matrix

• A square matrix A is skew-symmetric if $A^T = -A$ (also known as anti-symmetric or anti-Hermitian matrix).

Skew-Symmetric Matrix Example

• Example: $A = \begin{bmatrix} 0 & 2 & -3 \
• 2 & 0 & -6 \ 3 & 6 & 0 \end{bmatrix}$
• The diagonal elements of a skew-symmetric matrix are always zero.

Orthogonal Matrix

• A square matrix A is orthogonal if $AA^T = A^T A = I$

Singular and Non-Singular Matrix

• Singular matrix: A square Matrix where its determinant is zero. $|A| = 0$
• Non-singular matrix: A square matrix with a non-zero determinant. $|A| \neq 0$

Conformability for Addition

• Two matrices A and B are conformable for addition only if they have the same order.

Work

• The done by a force $\overrightarrow{F}$ on an object as it moves through a displacement $\overrightarrow{d\ell}$ is
• $dW = \overrightarrow{F} \cdot \overrightarrow{d\ell}$
• The total work done as the object moves from point A to point B:
• $W = \int_A^B \overrightarrow{F} \cdot \overrightarrow{d\ell}$
• If the force is constant and along the direction of displacement :
• $W = F \Delta \ell$
• SI unit : Newton-meter $(\text{N} \cdot \text{m}) = \text{Joule (J)}$

Example: Work done by gravity

• An object of mass $m$ moves from $y_A$ to $y_B$
• $W = \int_{y_A}^{y_B} \overrightarrow{F_g} \cdot \overrightarrow{d\ell}$
• $ = \int_{y_A}^{y_B} (-mg\hat{j}) \cdot (dy \hat{j})$
• $ = -mg \int_{y_A}^{y_B} dy$
• $=-mg (y_B - y_A)$
• $= mg(y_A - y_B)$
• the work done by gravity only depends on the change in height.

Kinetic Energy

• Consider the 1-D motion of a particle acted on by a force $F$. Newton's Second Law tells us $F = ma = m \frac{dv}{dt} = m \frac{dv}{dx} \frac{dx}{dt} = mv \frac{dv}{dx}$ so $F dx = mv dv$

• If the velocity changes from $v_A$ to $v_B$ then

• $W = \int_{x_A}^{x_B} F dx = \int_{v_A}^{v_B} mv , dv$

• $ = \frac{1}{2} m v_B^2 - \frac{1}{2} m v_A^2$

• Kinetic Energy defined as $K = \frac{1}{2} m v^2$

Work-Energy Relationship

• Then the work done is $W = \Delta K$ "Work changes Kinetic Energy"
• Result called Work-Energy Theorem

Ballistic Pendulum Example

• A projectile of mass $m$ is fired into a pendulum of mass $M$ where the projectile becomes embedded in the pendulum and momentum is conserved:
• $p_i = p_f$
• $mv = (M + m) V$
• $V = \frac{m}{M+m} v$

where $v$ is the initial velocity of the projectile and $V$ is the velocity of the (projectile + pendulum) just after the collision.

• Pendulum swings upward: Now we can its work-energy theorem with work done by gravity $= W = - (M+m) g h$ and change in kinetic energy $= \Delta K = 0 - \frac{1}{2} (M+m) V^2$
• So $-(M+m)gh = -\frac{1}{2} (M+m) V^2$
• $h = \frac{V^2}{2g} = \frac{1}{2g} (\frac{m}{M+m})^2 v^2$

Complex Numbers Definition

• Includes the imaginary unit $i = \sqrt{-1}$.
• Form of $a + bi$
• a and b are real numbers.
• Set of complex numbers is denoted by $\mathbb{C}$.

Complex Numbers Parts

• For $z= a + bi$:
• $a = Re(z)$ is the real part of z
• $b = Im(z)$ is the imaginary part of z

Complex Numbers Equality

• Two complex numbers $z_1 = a + bi$ and $z_2 = c + di$ are equal
• $a=c$ and $b=d$

Complex Number Operations

• $(a + bi) + (c + di) = (a + c) + (b + d)i$
• Commutative: $z_1 + z_2 = z_2 + z_1$
• Associative: $(z_1 + z_2) + z_3 = z_1 + (z_2 + z_3)$
• Identity: $z + 0 = z$, where $0 = 0 + 0i$
• Inverse: $z + (-z) = 0$, where $-z = -a - bi$

Complex Number Subtraction

$(a + bi) - (c + di) = (a - c) + (b - d)i$

Complex Number Multiplication

• $(a + bi)(c + di) = (ac - bd) + (ad + bc)i$
• Commutative: $z_1 \cdot z_2 = z_2 \cdot z_1$
• Associative: $(z_1 \cdot z_2) \cdot z_3 = z_1 \cdot (z_2 \cdot z_3)$
• Identity: $z \cdot 1 = z$, where $1 = 1 + 0i$
• Inverse: $z \cdot z^{-1} = 1$, where $z^{-1} = \frac{a}{a^2 + b^2} - \frac{b}{a^2 + b^2}i$, $z \neq 0$
• Distributive: $z_1 \cdot (z_2 + z_3) = z_1 \cdot z_2 + z_1 \cdot z_3$

Complex Number Division

• $\frac{a + bi}{c + di} = \frac{(a + bi)(c - di)}{(c + di)(c - di)} = \frac{(ac + bd) + (bc - ad)i}{c^2 + d^2}$

Complex Conjugate

• The complex conjugate of is denoted by and is defined as .
• $\overline{z_1 + z_2} = \bar{z_1} + \bar{z_2}$
• $\overline{z_1 \cdot z_2} = \bar{z_1} \cdot \bar{z_2}$
• $\overline{(\frac{z_1}{z_2})} = \frac{\bar{z_1}}{\bar{z_2}}$
• $z + \bar{z} = 2Re(z) = 2a$
• $z - \bar{z} = 2iIm(z) = 2bi$
• $z \cdot \bar{z} = a^2 + b^2$

Complex Number Modulus

• Also referred to as absolute value
• A complex number $z = a + bi$ as $|z| = \sqrt{a^2 + b^2}$.
• $|z| = |\bar{z}|$
• $|z_1 \cdot z_2| = |z_1| \cdot |z_2|$
• $|\frac{z_1}{z_2}| = \frac{|z_1|}{|z_2|}$
• $|Re(z)| \leq |z|$
• $|Im(z)| \leq |z|$
• $|z_1 + z_2| \leq |z_1| + |z_2|$ (Triangle Inequality)

Complex Polar Coordinate Form

• A complex number $z = a + bi$ can be $z = r(\cos\theta + i\sin\theta)$
• $r = |z| = \sqrt{a^2 + b^2}$ is the modulus of $z$

Complex Polar Coordinate Theta

• $\theta = arg(z)$ angle between the positive real axis and the line connecting the origin to the point $(a, b)$ in the complex plane.

Complex Euler's Formula

• $e^{i\theta} = cos\theta + i\sin\theta$ where the polar can be $z = re^{i\theta}$
• If $z_1 = r_1e^{i\theta_1}$ and $z_2 = r_2e^{i\theta_2}$, then:

Complex Polar Coordinate Operations

• $z_1 \cdot z_2 = r_1r_2e^{i(\theta_1 + \theta_2)}$
• $\frac{z_1}{z_2} = \frac{r_1}{r_2}e^{i(\theta_1 - \theta_2)}$
• $z^n = r^ne^{in\theta}$ (De Moivre's Theorem)

Complex Number Root

• The $n$-th roots of a complex number $z = re^{i\theta}$ are $w_k = \sqrt[n]{r}e^{i(\frac{\theta + 2\pi k}{n})}$ for $k = 0, 1, 2,..., n - 1$

Numerical Differentiation Approximations

• Derivative of a function approximated by value of function.
• Uniform grid $x_i = a + ih$, $i = 0, 1, \dots, N$, $x_0 = a$, $x_N = b$, $h = (b-a)/N$

Taylor Series Definition

$ f(x+h) = f(x) + f'(x)h + \frac{f''(x)}{2!}h^2 + \frac{f'''(x)}{3!}h^3 + \dots $

Forward Difference Definition

$ f'(x) \approx \frac{f(x+h) - f(x)}{h} $

• error is $ \frac{f''(\xi)}{2!}h = O(h) $

Backward difference Definition

$ f'(x) \approx \frac{f(x) - f(x-h)}{h} $

• error is $ \frac{f''(\xi)}{2!}h = O(h) $

Central Difference Definition

$ f'(x) \approx \frac{f(x+h) - f(x-h)}{2h} $

• error is $ O(h^2) $

High-order derivative

• $ f''(x) \approx \frac{f(x+h) - 2f(x) + f(x-h)}{h^2} $
• error is $ O(h^2) $

Tree: Definition and Properties

Tree Definition

• An undirected graph fulfilling one or more of requirements:
• It’s connected with no cycles.
• Has $n-1$ edges and no cycles.
• Any two vertices are connected by a simple path.

Rooted Tree Definition

• A rooted tree includes one specified node (the root).

Tree Terminology

• parent, child, sibling, ancestor, descendant are typical relationships
• Leaf: A node lacking children
• Subtree: A tree stemming from a node and its own descendants
• Path: A sequence of nodes $v_1, v_2,..., v_k$ so that $(v_i, v_{i+1}) \in E$ for all $1 \le i < k$
• Depth of node $v$: is the path length starting at root ending at the specified node.
• Height of node $v$: is the longest possible path from $v$ to a leaf
• Height of tree equals height of the root

Binary Tree Definition

• A type of Rooted trees
• Each node must have two or fewer children
• Children must be left or right assigned

Perfect Binary Tree Definition

• All nodes with children are required to two children
• All leaf nodes are required to be at same depth

Complete Binary Tree Definition

• Every level, except the last level is completely filled
• Last levels nodes, must go furthest the left

Tree Traversals

• Two ways of traversing:
• Depth-First Search (DFS)
• Breadth-First Search (BFS)

Depth-First Search Types

• Pre-order: visit self, left subtree, right subtree
• In-order: visit left, self, then right
• Post-order: visit left, right, self

Breadth-First Search Notes

• Visit all nodes at current depth, before exploring the next deepest level

Binary Search Tree (BST) Definition

• A binary tree
• For node $v$

BST Definition

• All nodes on its left are less than itself
• All nodes on its right must be greater than

Binary Search Tree Operations

• All run in $O(h)$ time:
• Search
• Insert
• Delete
• Min/Max
• Successor/Predecessor, where $h$ is the height of the tree

Balanced Search Trees

• To guarantee $O(\log n)$ operations: tree has to balanced out

List of Balanced Search Tress:

• AVL trees
• Red-black trees
• B-trees