Linear Algebra: Vector Spaces

Algèbre linéaire

Définitions de base

Espace vectoriel

• An vector space, denoted as $E$, is equipped with vector addition ($E \times E \rightarrow E$) and scalar multiplication ($\mathbb{K} \times E \rightarrow E$).
• Operations follow these properties: forms an abelian group, commutativity ($u + v = v + u$), associativity ($(u + v) + w = u + (v + w)$), existence of a zero vector ($0_E$), and existence of an additive inverse ($-u$).
• Scalar multiplication properties include: $\lambda(\mu u) = (\lambda \mu)u$, $(\lambda + \mu)u = \lambda u + \mu u$, $\lambda(u + v) = \lambda u + \lambda v$, and $1_{\mathbb{K}}u = u$.

Sous-espace vectoriel

• A subset $F$ of a vector space $E$ is a subspace if $0_E \in F$, $u + v \in F$ for all $u, v \in F$, and $\lambda u \in F$ for all $\lambda \in \mathbb{K}$ and $u \in F$.

Famille génératrice

• A set of vectors $(u_1,..., u_n)$ in $E$ is generating if every vector in $E$ can be written as a linear combination of these vectors.

Famille libre

• A set of vectors $(u_1,..., u_n)$ in $E$ is linearly independent if the only linear combination of these vectors that equals the zero vector is that where all coefficients are zero.

Base

• A basis of $E$ is a set of vectors that is both linearly independent and generating.

Dimension

• The dimension of $E$ is the number of vectors in a basis of $E$.

Applications linéaires

Définition

• A function $f : E \rightarrow F$ is linear if $f(u + v) = f(u) + f(v)$ and $f(\lambda u) = \lambda f(u)$ for all $u, v \in E$ and $\lambda \in \mathbb{K}$.

Noyau et image

• Kernel: $\operatorname{Ker}(f) = {u \in E \mid f(u) = 0_F}$.
• Image: $\operatorname{Im}(f) = {f(u) \mid u \in E}$.

Théorème du rang

• $\operatorname{dim}(E) = \operatorname{dim}(\operatorname{Ker}(f)) + \operatorname{dim}(\operatorname{Im}(f))$.

Matrices

Définition

• A matrix is a rectangular array of numbers.

Opérations

• Addition: $(A + B){ij} = A{ij} + B_{ij}$.
• Scalar multiplication: $(\lambda A){ij} = \lambda A{ij}$.
• Matrix multiplication: $(AB){ij} = \sum{k=1}^{n} A_{ik} B_{kj}$.

Transposée

• The transpose of $A$, denoted $A^T$, is defined by $(A^T){ij} = A{ji}$.

Inverse

• The inverse of $A$, denoted $A^{-1}$, satisfies $AA^{-1} = A^{-1}A = I$, where $I$ is the identity matrix.

Déterminant

• The determinant of $A$, denoted $\det(A)$, is a scalar that characterizes certain properties of the matrix.

Valeurs propres et vecteurs propres

• An eigenvector of $A$ is a vector $v$ such that $Av = \lambda v$, where $\lambda$ is an eigenvalue of $A$.

Produit scalaire

Définition

• An inner product on $E$ is a function $\langle \cdot, \cdot \rangle : E \times E \rightarrow \mathbb{K}$ that is linear in the first argument, symmetric (or Hermitian), and positive definite.
• Linear in the first argument: $\langle \lambda u + \mu v, w \rangle = \lambda \langle u, w \rangle + \mu \langle v, w \rangle$.
• Symmetric/Hermitian: $\langle u, v \rangle = \overline{\langle v, u \rangle}$.
• Positive definite: $\langle u, u \rangle > 0$ if $u \neq 0_E$.

Orthogonalité

• Two vectors $u$ and $v$ are orthogonal if $\langle u, v \rangle = 0$.

Funciones Vectoriales de Variable Real

Introducción

• Deals with vector functions of a real variable, which map real numbers to vectors in $\mathbb{R}^n$.
• Vector function $\overrightarrow{r}: I \subseteq \mathbb{R} \rightarrow \mathbb{R}^n$ assigns a vector $\overrightarrow{r}(t) = (f_1(t), f_2(t),..., f_n(t))$ to each real number $t$ in interval $I$.
• $f_i(t)$ are the component functions of $\overrightarrow{r}(t)$.
• $\overrightarrow{r}(t) = (t^2, \sin(t), e^t)$ is an example of a vector function with three components.

Límite y Continuidad

• The limit of $\overrightarrow{r}(t)$ as $t$ approaches $a$ is $\overrightarrow{L}$ if each component of $\overrightarrow{r}(t)$ tends to the corresponding component of $\overrightarrow{L}$ as $t$ approaches $a$.
• $\lim_{t \to a} \overrightarrow{r}(t) = \overrightarrow{L} = (\lim_{t \to a} f_1(t), \lim_{t \to a} f_2(t),..., \lim_{t \to a} f_n(t))$, provided that the limits of the components exist.
• A vector function $\overrightarrow{r}(t)$ is continuous at $t = a$ if $\overrightarrow{r}(a)$ is defined, $\lim_{t \to a} \overrightarrow{r}(t)$ exists, and $\lim_{t \to a} \overrightarrow{r}(t) = \overrightarrow{r}(a)$.

Derivada de una Función Vectorial

• The derivative of $\overrightarrow{r}(t)$ is defined as $\overrightarrow{r}'(t) = \lim_{h \to 0} \frac{\overrightarrow{r}(t+h) - \overrightarrow{r}(t)}{h} = (f_1'(t), f_2'(t),..., f_n'(t))$, provided that the limits of the components exist.
• $\overrightarrow{r}'(t)$ is tangent to the curve described by $\overrightarrow{r}(t)$ at the point $\overrightarrow{r}(t)$.
• Example: If $\overrightarrow{r}(t) = (t^2, \sin(t), e^t)$, then $\overrightarrow{r}'(t) = (2t, \cos(t), e^t)$.

Reglas de Derivación

• For differentiable vector functions $\overrightarrow{r}(t)$ and $\overrightarrow{u}(t)$, and a differentiable scalar function $f(t)$:
  • $\frac{d}{dt} [\overrightarrow{r}(t) + \overrightarrow{u}(t)] = \overrightarrow{r}'(t) + \overrightarrow{u}'(t)$
  • $\frac{d}{dt} [c\overrightarrow{r}(t)] = c\overrightarrow{r}'(t)$, where $c$ is a constant.
  • $\frac{d}{dt} [f(t)\overrightarrow{r}(t)] = f'(t)\overrightarrow{r}(t) + f(t)\overrightarrow{r}'(t)$
  • $\frac{d}{dt} [\overrightarrow{r}(t) \cdot \overrightarrow{u}(t)] = \overrightarrow{r}'(t) \cdot \overrightarrow{u}(t) + \overrightarrow{r}(t) \cdot \overrightarrow{u}'(t)$
  • $\frac{d}{dt} [\overrightarrow{r}(t) \times \overrightarrow{u}(t)] = \overrightarrow{r}'(t) \times \overrightarrow{u}(t) + \overrightarrow{r}(t) \times \overrightarrow{u}'(t)$
  • $\frac{d}{dt} [\overrightarrow{r}(f(t))] = \overrightarrow{r}'(f(t))f'(t)$ (Chain Rule)

Integral de una Función Vectorial

• The indefinite integral of $\overrightarrow{r}(t)$ is defined component-wise: $\int \overrightarrow{r}(t) dt = (\int f_1(t) dt, \int f_2(t) dt,..., \int f_n(t) dt) + \overrightarrow{C}$, vector $\overrightarrow{C}$ being a constant of integration.
• For definite integral of $\overrightarrow{r}(t)$ on the interval $[a, b]$: $\int_a^b \overrightarrow{r}(t) dt = (\int_a^b f_1(t) dt, \int_a^b f_2(t) dt,..., \int_a^b f_n(t) dt)$.
• Example: If $\overrightarrow{r}(t) = (t^2, \sin(t))$, then $\int \overrightarrow{r}(t) dt = (\frac{t^3}{3} + C_1, -\cos(t) + C_2)$.

Aplicaciones

• Vector functions have uses in physics and engineering for motion description, calculation of velocity and acceleration, and in designing curves as well as surfaces.

3D Γραφικά Υπολογιστών

Εισαγωγή

• Coordinates: Screen $(x, y)$, Depth $z$, Color (Red, Green, Blue)

Σωληνογραμμή

Κορυφές

• Vertex Generation, Vertex Transformation

Συναρμολόγηση

• Triangle Assembly

Ραστεροποίηση

• Triangle Rasterization

Εικονοστοιχεία

• Pixel Shading, Pixel Blending

Ευρεσιακή Σκίαση

Διάχυτη Ανάκλαση

• The position of light, surface position and normal vector are all factors.
• $L_{\text{diffuse}} = k_d I \max(0, \mathbf{n} \cdot \mathbf{l})$
  • $k_d$: Diffuse reflection coefficient
  • $I$: Light intensity
  • $\mathbf{n}$: Unit surface normal vector
  • $\mathbf{l}$: Unit vector towards the light source

Κατοπτρική Ανάκλαση

• $L_{\text{specular}} = k_s I \max(0, \mathbf{v} \cdot \mathbf{r})^p$
• $k_s$: Specular reflection coefficient
• $I$: Light intensity
• $\mathbf{v}$: Unit vector towards the camera
• $\mathbf{r}$: Unit reflected vector
• $p$: Shininess exponent

Νόμος Ανάκλασης

• $\mathbf{r} = 2(\mathbf{n} \cdot \mathbf{l})\mathbf{n} - \mathbf{l}$

Γραμμική Άλγεβρα για Γραφικά Υπολογιστών

Σημείο

• Definition: Position in space
• It has just position.

Διάνυσμα

• Definition: Has direction and magnitude
• It doesnt have position.
• Can be added to a point to move it.

Γραμμές

• $\mathbf{v} = P_2 - P_1$
• $P(t) = P_1 + t\mathbf{v}, \quad t \in [0, 1]$

Τρίγωνα

• Three points exist
• Internal/External
• Normal Vector
• Exists within a Plane.

Επίπεδο

• Point $P_0$ and normal vector $\mathbf{n}$ exist
• All points $P$ on the plane satisfy: $\mathbf{n} \cdot (P - P_0) = 0$

Εσωτερικό Γινομένο

• $\mathbf{a} \cdot \mathbf{b} = |\mathbf{a}||\mathbf{b}|\cos(\theta)$
• Finds the angle between 2 vectors
• Vector projection to another

Εξωτερικό Γινόμενο

• $\mathbf{a} \times \mathbf{b} = |\mathbf{a}||\mathbf{b}|\sin(\theta)\mathbf{n}$
• Used for: vector vertical to 2 vectors calculation, the surface of a parallelogram calculation

Μήκος Διανύσματος

• $|\mathbf{a}| = \sqrt{\mathbf{a} \cdot \mathbf{a}}$

Ορθοκανονικοποίηση

• Process for creating orthogonal and normalized vector sets from linear independent vector sets
• Gram-Schmidt method

Μήτρες

• Transformations include: Rotation, Scaling, Translation and Projection.

Βασικές Μήτρες

• Scaling: $$ \begin{bmatrix} s_x & 0 & 0 \ 0 & s_y & 0 \ 0 & 0 & s_z \end{bmatrix} $$
• Rotation around $x$: $$ \begin{bmatrix} 1 & 0 & 0 \ 0 & \cos(\theta) & -\sin(\theta) \ 0 & \sin(\theta) & \cos(\theta) \end{bmatrix} $$
• Matrix Multiplication
• Matrix Inversion
• Matrix Transposition
• Matrix Determinant

Ομογενείς Συντεταγμένες

• Involves 4D vectors and matrices used to represent 3D transformations
• Allows Translation to be represented as matrix multiplication

Μεταφορά

• Translation: $$ \begin{bmatrix} 1 & 0 & 0 & t_x \ 0 & 1 & 0 & t_y \ 0 & 0 & 1 & t_z \ 0 & 0 & 0 & 1 \end{bmatrix} $$

Προβολή

• Conversion of 3D to 2D screen
• Orthographic Projection
• Perspective Projection

Ορατότητα

Z-Buffer

• The Z-buffer stores the depth of each pixel.
• A new pixel that is closer to the camera than the current one replaces it inside the Z-buffer

Backface Culling

• Rejection of triangles facing backwards
• The normals need to be calculated for each triangle
• If the normal is facing away the triangle is rejected

Algorithmic Game Theory Lecture 1

Game Theory Definition

• The study of mathematical models of strategic interactions among rational agents.
• Agents can be people, companies, algorithms, etc.
• Rationality equals the agents desire to maximize own utility.
• Strategic interaction: one's actions affects another.

Example: Prisoner's Dilemma

• Two suspects arrested cannot get convicted due to lack of evidence so they get interrogated separately. Confessing and denying results in freedom for the former, and 10 years prison for the latter. Confessing results in 5 years while denying results in 1 year sentence.

Algorithmic Game Theory

• Intersection of game theory and computer science.
• It uses CS tools analyzing games, and uses GT framework to design systems with strategic agents.

Example: Sponsored Search Auction

• Advertisers bid on keywords, then when a user searches for a keyword, the auction is run to determine the best ad to show. The user pays and the goals are to maximize the revenue, user satisfaction and advertisers' utility.

Selfish Routing

• Involves a network($G = (V, E)$), latency function ($l_e(x)$ is the latency when the load is $x$) and the traffic rate between pairs of nodes. The social cost is $\sum_{e \in E} f_e \cdot l_e(f_e)$, where $f_e$ is the amount of flow on edge $e$.

Example: Braess's Paradox

• With a dashed line, the traffic going from 1 path to the other causes increase in cost.

Topics

Topics That Will Be Covered

• Solution Concepts
• Mechanism Design
• Social Networks
• Learning in Games
• Fair Division

Solution Concepts

• Nash Equilibrium: A set of strategies optimal such that a player cant change their strategy on their own to result better.
• Approximate Nash Equilibrium: A set of strategies, one for each player, such that no player can improve their utility by more than $\epsilon$ by unilaterally changing their strategy.
• Correlated Equilibrium: A probability distribution over strategy profiles that prevents players benefiting from changing strategy.

Lecture 19: Particle on a Ring

Schrödinger equation

• Time-independent Schrödinger equation is given as: $-\frac{\hbar^2}{2I} \frac{d^2}{d\phi^2} \Theta (\phi) = E\Theta (\phi)$
  • $I = mr^2$ is the moment of inertia
  • $\Theta (\phi) = A e^{im\phi}$
  • $E = \frac{\hbar^2 m^2}{2I} = \frac{\hbar^2 m^2}{2mr^2}$

Boundary condition

• Cyclic boundary condition requires $\Theta (\phi) = \Theta (\phi + 2\pi)$
  • Applying this condition gives $m = k = 0, \pm 1, \pm 2,...$
  • Quantized energy levels are $E = \frac{\hbar^2 k^2}{2I}$

Wavefunctions

• Normalized wavefunctions are $\Theta_k (\phi) = \frac{1}{\sqrt{2\pi}} e^{ik\phi}$, $k = 0, \pm 1, \pm 2,...$
  • Probability normalization is $\int_0^{2\pi} \Theta_k^* (\phi) \Theta_k (\phi) d\phi = 1$

Operators

Kinetic energy

• Kinetic energy operator $\hat{T} = -\frac{\hbar^2}{2I} \frac{d^2}{d\phi^2}$
  • Applying to the wavefunction gives $\hat{T} \Theta_k (\phi) = \frac{\hbar^2k^2}{2I} \Theta_k (\phi)$

Angular momentum

• Angular momentum operator $\hat{L_z} = -i\hbar \frac{d}{d\phi}$
  • Applying to the wavefunction gives $\hat{L_z} \Theta_k (\phi) = \hbar k \Theta_k (\phi)$

Expectation values

• Expectation value of angular momentum $\langle \hat{L_z} \rangle = \hbar k$
• Expectation value of angular momentum squared $\langle \hat{L_z}^2 \rangle = (\hbar k)^2$
• Variance of angular momentum $\sigma_{L_z}^2 = \langle \hat{L_z}^2 \rangle - \langle \hat{L_z} \rangle ^2 = 0$

Uncertainty

• Uncertainty in angular momentum $\sigma_{L_z} = 0$
• Expectation value of angular position $\langle \phi \rangle = \pi$
• Expectation value of angular position squared $\langle \phi^2 \rangle = \frac{4\pi^2}{3}$
• Variance of angular position $\sigma_{\phi}^2 = \langle \phi^2 \rangle - \langle \phi \rangle ^2 = \frac{\pi^2}{3}$
• Uncertainty in angular position $\sigma_{\phi} = \frac{\pi}{\sqrt{3}}$

Chapter 5: Problem Set

General Instructions

• Create a specific directory per problem.
• A README file with problem description/compilation included within

Problems

Floating Point Numbers

• Problem involves to sum a set of floating point numbers from standard input storing set inside double array, then after 10 runs recording the change of execution time with the -O3 flag

Root Finding

• The question's about forming a findroot function using Newton's method with function pointer, derivation, initial guess, etc. Testing requires a degree of tolerance and iterations.

Algorithmic Trading and Order Execution

Algorithmic Trading

• Employs computer programs to follow a defined set of instructions (an algorithm) for placing a trade.
• Algorithms can execute a trade at a speed and frequency impossible for human trader.
• Useful for Institutional/Investment and Hedge funds.
• Reasons for usage includes: Costs, speed, simultaneity, time extensions beyond market hours, profits, accuracy, impacts.

Algorithmic Trading Strategies

• Trend Following Strategies involves detecting the direction of a trend and trading in that direction until the trend reverses.
• Mean Reversion Strategies trade where price tends to revert based on overbought or oversold conditions.
• Arbitrage Strategies exploit price differences for the same asset in different markets or forms by simultaneously buying and selling.
• Index Fund Rebalancing maintains the composition of the underlying index.
• Mathematical Model-Based Strategies employs complex math to identify trading opportunities from stats.
• Order Execution Algorithms minimizes market impact and transaction costs by breaking it down.

Order Execution

Order Placement Considerations

• Buy and sell side seek oppositive things, where sell side is fast with best and buy side wants lower commisions.

Types of Order

• Market Order executes immediately at the current market price.
• Limit Order executes at a specified price or better.
• Stop Order turns to market order once the stop price is reached.
• Stop-Limit Order turns to limit order one the stop price is reached.
• Market-on-Close (MOC) Order is as close as possible to closing price
• Limit-on-Close (LOC) Order is a limit order as close as possible to closing price.

Order Instructions

• Day Order expires if unexecuted on that day.
• Good-Til-Cancelled (GTC) Order means persistance through executions/cancellations
• Immediate-or-Cancel (IOC) Order cancels anything that cant be executed immediatelly
• Fill-or-Kill (FOK) Order does a cancles if there isnt a full execution
• All-or-None (AON) Order executes entirely, but not necessarily immediately.

Order Execution Algorithms

• VWAP (Volume Weighted Average Price) executes to market volume
• TWAP (Time Weighted Average Price) executes to amount of a period
• Percentage of Volume (POV) allows the order to track market
• Implementation Shortfall minimizes difference compared to the expected

Dark Pools

• Private exchanges for trading securities

Gaming

• Practice of exploiting order execution algorithms for profit

Regulatory Oversight

• Bodies such as the SEC and FINRA look over