Linear Algebra - Matrix Vector (Multiplication)

Card Puncher Data Processing

About

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 <math>r \in \mathbb{R}</math> .

<MATH> v[r] = \sum_{k \in C} (M[r,c]u[c]) </MATH>

Algebraic properties

Let A be an R x C matrix:

  • For any C-vector v and any scalar <math>\alpha</math> ,

<MATH> A*( \alpha v) = \alpha ( A * v) </MATH>

  • For any C-vector u and v:

<MATH> A*( u + v) = A * u + A * v </MATH>

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)

<MATH> M * v_c = \sum_{c \in C} ( v[c]*(columnVector_c \text{ of } M )) </MATH>

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

  • R-vector

<MATH> v_r * M = \sum_{r \in R} ( v_r[r]*(rowVector_r \text{ of } M)) </MATH>

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

  • Others (???)

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

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:

<math>\begin{bmatrix}a & c \\ b & d \end{bmatrix} * \begin{bmatrix}x \\ y \end{bmatrix} = \begin{bmatrix}p \\ q \end{bmatrix}</math>

  • Solution:

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

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. <MATH>v = [\text{for each } r \in R: v[r] = (row_r \text{ of } M) * u]</MATH>

Example: <MATH> \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} </MATH>

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]:

<MATH> \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] </MATH>

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

<MATH> \text{for i in R:} \\ v[i] := \sum_{j \in C} M[i,j]u[j] </MATH>

  • 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
Card Puncher Data Processing
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,...
Card Puncher Data Processing
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...
Card Puncher Data Processing
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...
Card Puncher Data Processing
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...
Card Puncher Data Processing
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...
Matrix Matrix Multplication
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...
Card Puncher Data Processing
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...
Card Puncher Data Processing
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...
Card Puncher Data Processing
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...
Image Vector
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...



Share this page:
Follow us:
Task Runner