Basic Matrix Operations

Transpose: A^T

• Algorithm: A^T[i,j] = A[j,i], exchange the row and column indices.
• # operations $= \Theta(mn)$

Scalar multiplication: $c \cdot A_{m\times n}$

• Precondition: c is a real number.
• Algorithm: $(c \cdot A)[i,j] = c \cdot A[i,j]$, multiply each element of A by c.
• # operations $= \Theta(mn)$

Addition: $A_{m \times n} + B_{m \times n}$

• Precondition: A and B have the same shape.
• Algorithm: (A + B)[i,j] = A[i,j] + B[i,j], add element by element.
• # operations $= \Theta(mn)$

Dot product (of vectors): u^T v

• Preconditions:
  • A row vector (u^T) times a column vector (v);
  • Two vectors have the same size (n).
• Algorithm: $u^T v = u_1 v_1 + u_2 v_2 + \cdots + u_n v_n \equiv \sum_{i=1}^n u_i v_i$
• # operations $= \Theta(n)$

Norm (l²-norm) of a vector: $\Vert u \Vert = \sqrt{u^T u}$.

How can we express matrix subtraction in terms of these operations?