# Matrix
A **matrix** is a two-dimensional rectangular array of values organised in rows and columns.

In C, a matrix is stored as a flat [[array]] in **row-major order**: all elements of row 0 come first, then row 1, and so on. The element at row `i`, column `j` of an `M × N` matrix sits at index `i * N + j` in the flat array. This layout makes row traversal cache-friendly (consecutive elements are adjacent in memory) and column traversal cache-unfriendly (stride N between elements).

```c
// 3×4 matrix of doubles
double A[3][4];

// access element at row 1, column 2
A[1][2] = 3.14;

// equivalent flat-index access on a pointer
double *flat = &A[0][0];
flat[1 * 4 + 2] = 3.14;
```

Matrix operations form the core of numerical computing and machine learning. Matrix-vector multiplication ($y = Ax$, $O(mn)$) and matrix-matrix multiplication ($C = AB$, $O(mnk)$) are the workhorses. Naive loop implementations leave significant performance on the table; high-performance implementations (BLAS, LAPACK) exploit SIMD, cache blocking, and multi-threading to approach peak hardware throughput.

**Sparse matrices** store only non-zero entries for matrices where most elements are zero. Common formats are CSR (Compressed Sparse Row) and CSC (Compressed Sparse Column), which store a flat array of non-zero values alongside arrays of column indices and row-start offsets. Sparse formats reduce both memory and compute by skipping zero entries, at the cost of indirect addressing.

| Operation | Time |
|---|---|
| Access element | O(1) |
| Matrix-vector multiply | O(mn) |
| Matrix-matrix multiply | O(mnk) |
| Transpose (in-place) | O(mn) |