# Linear Algebra - Matrix Vector (Multiplication)

There is two ways to multiply a matrix by a vector:

• matrix vector
• or vector matrix

For each of these multiplication, two equivalent implementations (definitions):

## Definition

### Ordinary

“Ordinary” Definition of Matrix-Vector Multiplication: If M is an R x C matrix and u is a C-vector then M * u is the R-vector v such that, for each $r \in \mathbb{R}$ .

$$v[r] = \sum_{k \in C} (M[r,c]u[c])$$

### Algebraic properties

Let A be an R x C matrix:

• For any C-vector v and any scalar $\alpha$ ,

$$A*( \alpha v) = \alpha ( A * v)$$

• For any C-vector u and v:

$$A*( u + v) = A * u + A * v$$

## Type

### Linear Combination

Linear Combination definitions for a matrix-vector multiplication with a matrix M (RxC).

If the vector is a:

• C-vector (If v is not a C-vector then error)

$$M * v_c = \sum_{c \in C} ( v[c]*(columnVector_c \text{ of } M ))$$

$$\begin{pmatrix} 1 & 2 & 3 \\ 10 & 20 & 30 \end{pmatrix} * [7,0,4] = 7 * [1,10] + 0 * [2,20] + 4 * [3,30]$$

• R-vector

$$v_r * M = \sum_{r \in R} ( v_r[r]*(rowVector_r \text{ of } M))$$

$$[7,4] * \begin{pmatrix} 1 & 2 & 3 \\ 10 & 20 & 30 \end{pmatrix} = 7 * [1,2,3] + 4 * [10,20,30]$$

• Others (???)

$$\begin{pmatrix} 1 & 2 & 3 \\ 10 & 20 & 30 \end{pmatrix} * [1,0.5,2] = \begin{pmatrix} 8 \\ 75 \end{pmatrix}$$

#### Application

Fundamental Computational Problem: Solving a linear matrix-vector equation

• input: an R x C matrix A and an R-vector b
• output: the C-vector x such that A * x = b

Problem:

• Simple formula to solve:

$\begin{bmatrix}a & c \\ b & d \end{bmatrix} * \begin{bmatrix}x \\ y \end{bmatrix} = \begin{bmatrix}p \\ q \end{bmatrix}$

• Solution:

$\text{if } ad \neq bc: x = \frac{\displaystyle dp - cq}{\displaystyle ad - bc} \text{ and } y = \frac{\displaystyle aq - bp}{\displaystyle ad - bc}$

A algorithm for solving a matrix-vector equation can be use to solve a vector-matrix equation, using transpose.

### Dot Product

The Dot Product Definition of matrix-vector multiplication is the multiplication of two vectors applied in batch to the row of the matrix.

Let M be an R x C matrix, M * u is the R-vector v such that v[r] is the dot-product of row r of M with u. $$v = [\text{for each } r \in R: v[r] = (row_r \text{ of } M) * u]$$

Example: $$\begin{array}{rcl} \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ 10 & 0 \end{bmatrix} * [3,-1] & = & [ [1, 2].[3,-1], [3, 4].[3,-1], [10, 0].[3,-1] ] \\ & = & [ 1,5,30 ] \end{array}$$

#### Applications of dot-product

• Downsampling: Each pixel of the low-res image corresponds to a little grid of pixels of the high-res image. The intensity value of a low-res pixel is the average of the intensity values of the corresponding high-res pixels. Averaging can be expressed as dot-product. We want to compute a dot-product for each low-res pixel. Can be expressed as matrix-vector multiplication.
• blurring: To blur a face, replace each pixel in face with average of pixel intensities in its neighborhood. Average can be expressed as dot-product. By dot-product definition of matrix-vector multiplication, can express this image transformation as a matrix-vector product. Gaussian blur: a kind of weighted average
• Audio search: Lots of dot-products, Represent as a matrix-vector product, One row per dot-product. To search for [0,1,-1] in in [0, 0,−1, 2, 3,−1, 0, 1,−1,−1]:

$$\begin{bmatrix} \begin{array}{rrr} 0 & 0 & -1 \\ 0 & -1 & 2 \\ -1 & 2 & 3 \\ 2 & 3 & -1 \\ 3 & -1 & 0 \\ -1 & 0 & 1 \\ 0 & 1 & -1 \\ 1 & -1 & -1 \end{array} \end{bmatrix} * [0,1,-1]$$

## Computation

To compute matrix-vector or vector-matrix product, we could use dot-product or linear-combinations definition. However, using those definitions, it’s not easy to exploit sparsity in the matrix.

• Without using sparsity

$$\text{for i in R:} \\ v[i] := \sum_{j \in C} M[i,j]u[j]$$

• Using sparsity in the matrix
initialize v to zero vector
for each pair (i , j) in sparse representation,
v[i] = v[i] + M[i,j] u[j]


Discover More
Geometry - Scaling

Scaling is a transformation that is generally applied by the transformation matrix See also: The functional form becomes the following matrix. Using the standard transformation matrix notation,...
Linear Algebra - Basis of a Vector Space

A basis for vector space V is a linearly independent set of generators for V. Thus a set S of vectors of V is a basis for V if S satisfies two properties: Property B1 (Spanning) Span S = V, and Property...
Linear Algebra - Coordinate system

coordinate system in terms of vector. Idea of coordinate system for a vector space V: (and generalized beyond two dimensions), Coordinate system for a vector space V is specified by generators of...
Linear Algebra - Find a basis computation problem

Find a basis for a vector space Example: Find a basis for the null space of By the dot-product definition of matrix-vector multiplication, a vector v is in the null space of A if the dot-product...
Linear Algebra - Matrix

The Traditional notion of a matrix is: a two-dimensional array a rectangular table of known or unknown numbers One simple role for a matrix: packing together a bunch of columns or rows Matrix...
Linear Algebra - Matrix Matrix (Multiplication)

Matrix Matrix (Multiplication) definition . Two matrices may be multiplied when they are conformable: ie the number of columns in the first matrix is equal to the number of rows in the second matritransposevector-matrix...
Linear Algebra - Null Space of a (Matrix|Vector Space)

Null space of a matrix A (Written Null A) is: The Null space of a matrix is a basis for the solution set of a homogeneous linear system that can then be described as a homogeneous matrix equation. A...
Linear Algebra - Span of a Vector Space

The set of all linear combinations of some vectors v1,...,vn is called the span of these vectors and contains always the origin. Example: Let V = Span {[0, 0, 1], [2, 0, 1], [4, 1, 2]}. A vector belongs...
Linear Algebra - Triangular Matrix

The matrix is a triangular matrix. Definition: An n x n upper triangular matrix A is a matrix with the property that . The entries forming the triangle can be be zero or nonzero. We can use backward substitution...
Linear Algebra - Vector

tuple in Linear algebra are called vector. A vector is a list of scalar (real number) used to represent a When the letters are in bold in a formula, it signifies that they're vectors, To represent...