Matrix Theory | Rod Carvalho

Posts Tagged ‘Matrix Theory’

Matrix decompositions with sparsity constraints

December 12, 2008

Suppose we are given a finite square matrix $A \in \mathbb{R}^{n \times n}$ . We would like to factorize $A$ into $N$ (where $N$ is finite) matrices

$A = W_{N-1} W_{N-2} \ldots W_ {2} W_{1} W_{0}$ ,

where factors $W_0, W_1, \ldots, W_{N-1} \in \mathbb{R}^{n \times n}$ are required to have a certain sparsity pattern, i.e., a subset of their $n^2$ entries must be zero.

Definition: Let $\mathcal{I}_n = \{1, 2, \ldots, n\}$ and $\mathcal{I}_n^2 = \mathcal{I}_n \times \mathcal{I}_n$ . A sparsity pattern $\mathcal{S}_n$ is a set of ordered pairs $(i,j) \in \mathcal{I}_n^2$ that indicate which entries of a $n \times n$ matrix are constrained to be zero.

Note that $\mathcal{S}_n \subseteq \mathcal{I}_n^2$ . If there are no sparsity constraints, then $\mathcal{S}_n$ is an empty set. Set $\mathcal{I}_n^2 \setminus \mathcal{S}_n$ contains the indices of the entries of a $n \times n$ matrix which are unconstrained, i.e., “free”.

__________

Problem: Given a matrix $A \in \mathbb{R}^{n \times n}$ and a particular sparsity pattern $\mathcal{S}_n$ , how can we find if it is possible to factorize $A$ into $N$ factor matrices (where $N$ is finite) whose sparsity pattern is the specified one? If such factorization is possible, how can we compute each factor $W_1, W_2, \ldots, W_{N-1}$ and $N$ ?

__________

This problem is easy to pose, but I have found it very hard to attack. I have tried various approaches… and none worked. Does anyone have any ideas?

__________

Example: suppose we are given a $5 \times 5$ real matrix

$A = \left[\begin{array}{ccccc} 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ \end{array}\right]$ .

We would like to factorize matrix $A$ into $N$ factors $\{W_k\}_{k =0}^{N-1} \in \mathbb{R}^{5 \times 5}$ whose sparsity pattern is represented pictorially by

$\left[\begin{array}{ccccc} \times & \times & 0 & 0 & 0\\ \times & \times & \times & 0 & 0\\ 0 & \times & \times & \times & 0\\ 0 & 0 & \times & \times & \times\\ 0 & 0 & 0 & \times & \times\\\end{array}\right]$ ,

where a “ $\times$ ” in the $(i,j)$ entry means that the $(i,j)$ entry is unconstrained, i.e., it is allowed to take any value in $\mathbb{R}$ . If you are familiar with numerical PDE’s, you certainly encountered matrices with this sparsity pattern when solving diffusion or wave equations in one spatial dimension using finite difference methods.

__________

Even though this example seems fairly “simple” (it’s only a $5 \times 5$ matrix after all!), I have not yet found an approach that works.

Tags:Mathematics, Matrix Decompositions, Matrix Theory, Sparsity
Posted in Mathematics | 11 Comments »

Representing complex numbers as 2×2 matrices

November 9, 2008

We can represent complex numbers as $2 \times 2$ real matrices, such that arithmetic operations $(+, -, \times, \div)$ on complex numbers become equivalent to arithmetic operations on their matrix representations.

Consider a matrix-valued function $M: \mathbb{C} \rightarrow \mathbb{R}^{2 \times 2}$ defined as

$M(z) = \left[\begin{array}{cc} \Re\{z\} & -\Im\{z\}\\ \Im\{z\} & \Re\{z\}\\ \end{array}\right]$ ,

where $\Re\{z\}$ and $\Im\{z\}$ are the real and imaginary parts of $z \in \mathbb{C}$ , respectively. It can be shown that for all $z_1, z_2 \in \mathbb{C}$ , we have that

$M(z_1 + z_2) = M(z_1) + M(z_2)$ .

$M(z_1 - z_2) = M(z_1) - M(z_2)$ .

$M(z_1 z_2) = M(z_1) M(z_2)$ .

$M(z_1 / z_2) = [M(z_2)]^{-1} M(z_1)$ , if $z_2 \neq 0$ .

There seems to be an homomorphism here.

__________

Matrix Representation of a Complex Number

Let $z = a + i b$ , where $i = \sqrt{-1}$ and $a,b \in \mathbb{R}$ , be a complex number. Its matrix representation is

$M(z) = M(a + i b) = \left[\begin{array}{cc} a & -b\\ b & a\\ \end{array}\right] = a \left[\begin{array}{cc} 1 & 0\\ 0 & 1\\ \end{array}\right] + b \left[\begin{array}{cc} 0 & -1\\ 1 & 0\\ \end{array}\right]$ .

Let matrices $I_2, Q \in \mathbb{R}^{2 \times 2}$ be

$I_2 = \left[\begin{array}{cc} 1 & 0\\ 0 & 1\\ \end{array}\right], \quad{} Q = \left[\begin{array}{cc} 0 & -1\\ 1 & 0\\ \end{array}\right]$ ,

then the matrix representation of $z \in \mathbb{C}$ is

$M(z) = M(a + i b) = a I_2 + b Q$ .

Note that both $I_2$ and $Q$ are orthogonal matrices, and therefore $Q^{-1} = Q^T$ . Since $I_2$ is the $2 \times 2$ identity matrix, we have that $I_2$ and $Q$ commute, i.e., $I_2 Q = Q I_2$ .

The matrix representation of the complex conjugate of $z$ is

$M(z^*) = M(a - i b) = a I_2 - b Q = M^T (z)$ ,

which follows from the fact that matrix $Q$ is skew-symmetric, i.e., $Q^T = -Q$ . The complex conjugate of a complex number can thus be computed by transposing its matrix representation. Since $Q^T = Q^{-1}$ and $Q^T = - Q$ , we have $Q^2 = - I_2$ .

The square of the magnitude of a complex number, $|z|^2 = zz^*$ , is equal to the determinant of its matrix representation, as follows

$\det(M(z)) = \det(M(a + i b)) = \begin{vmatrix} a & -b \\ b & a\\ \end{vmatrix} = a^2 + b^2 = |z|^2$ .

A complex number written in the cartesian form, $z = a + i b$ , can be converted to its polar form, $z = \rho e^{i \theta}$ , where $\rho = \sqrt{a^2 + b^2}$ and $\theta = \arg(z)$ . Given a complex number in the polar form $z = \rho e^{i \theta}$ , its cartesian form is

$z = \rho (\cos(\theta) + i \sin(\theta))$ ,

and its matrix representation is

$M(z) = \rho \left[\begin{array}{cc} \cos(\theta) & -\sin(\theta)\\ \sin(\theta) & \cos(\theta)\\ \end{array}\right] = \rho R(\theta)$ ,

where

$R(\theta) = \left[\begin{array}{cc} \cos(\theta) & -\sin(\theta)\\ \sin(\theta) & \cos(\theta)\\ \end{array} \right]$

is a rotation matrix that rotates a vector in $\mathbb{R}^2$ by a counterclockwise angle $\theta$ radians, leaving the vector’s $\|\cdot\|_2$ unchanged. Matrix $R(\theta)$ is orthogonal, and thus $R^{-1} (\theta) = R^T (\theta)$ . Given that

$\sin(-\theta) = - \sin(\theta), \quad{} \cos(-\theta) = \cos(\theta)$ ,

we have $R(-\theta) = R^T (\theta) = R^{-1}$ . As $\det(R(\theta)) = 1$ for any value of $\theta$ , we can conclude that $R(\theta) \in \text{SO}(2)$ .

Finally, note that $Q = R(\frac{\pi}{2})$ , i.e., matrix $Q$ rotates a vector in $\mathbb{R}^2$ $\pi/2$ radians counter-clockwise. If we multiply a complex number by $i$ , we rotate it by a counterclockwise angle of $\pi/2$ radians

$i z = i \rho e^{i \theta} = \rho e^{i (\theta + \frac{\pi}{2})}$ ,

and in terms of matrix representations, this is equivalent to multiplying $M(z)$ by matrix $Q$ . It does not matter if we multiply by $Q$ on the left or on the right, because matrices $I_2$ and $Q$ do commute.

__________

Arithmetic Operations

Let $z_1 = a_1 + i b_1$ and $z_2 = a_2 + i b_2$ be two complex numbers. Their addition/subtraction is thus

$z_1 \pm z_2 = (a_1 \pm a_2) + i (b_1 \pm b_2)$ ,

and from the rules of matrix addition / subtraction it can easily be shown that $M(z_1) \pm M(z_2) = M(z_1 \pm z_2)$ .

It’s easier to compute products of complex numbers if we write them in the polar form, i.e., $z_1 = \rho_1 e^{i \theta_1}$ and $z_2 = \rho_2 e^{i \theta_2}$ . The product is thus $z_1 z_2 = \rho_1 \rho_2 e^{i (\theta_1 + \theta_2)}$ . The product of the matrix representations is

$M(z_1) M(z_2) = \rho_1 R(\theta_1) \rho_2 R(\theta_2) = \rho_1 \rho_2 R(\theta_1 + \theta_2) = M(z_1 z_2)$ ,

since $R(\theta_1) R(\theta_2) = R(\theta_1 + \theta_2)$ . Dividing $z_1 \in \mathbb{C}$ by $z_2 \in \mathbb{C} \setminus \{0\}$ yields

$\displaystyle\frac{z_1}{z_2} = \frac{\rho_1}{\rho_2} e^{i (\theta_1 - \theta_2)}$ ,

whose corresponding matrix representation is

$\displaystyle M(z_1 / z_2) = \frac{\rho_1}{\rho_2} R(\theta_1 - \theta_2)$ .

Note that

$M^{-1} (z_2) M(z_1) = \displaystyle \frac{\rho_1}{\rho_2} R(-\theta_2) R(\theta_1) = \frac{\rho_1}{\rho_2} R(\theta_1 - \theta_2)$

and therefore $M^{-1} (z_2) M(z_1) = M(z_1 / z_2)$ .

We can conclude that arithmetic operations on complex numbers are equivalent to arithmetic operations on the matrices representing such complex numbers.

I have absolutely no idea what use this matrix representation could possibly have, but it’s quite interesting nonetheless.

__________

Complex Numbers as Matrices

Tags:Complex Numbers, Linear Algebra, Mathematics, Matrix Theory
Posted in Mathematics | 10 Comments »

Gilbert Strang’s lectures on Linear Algebra

October 16, 2008

Matrix theory is the arithmetic of higher mathematics.

–Richard Bellman (1920-1984)

Prof. Gilbert Strang‘s famous lectures on Linear Algebra are available for download here. You can also watch the 34 lectures on YouTube. More material can be found on the course’s OCW page. Highly recommended. Strang is an awesome teacher. His lectures are delightful.

Thanks to MIT OCW for making the lecture available online.

__________

MIT leads elite colleges offering free resources (Dec. 2007)

Online university courses big hit (Dec. 2007)

Tags:Gilbert Strang, Linear Algebra, Matrix Theory, MIT, MIT OCW
Posted in Mathematics | Leave a Comment »

S	M	T	W	T	F	S
« Dec
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

Rod Carvalho

Posts Tagged ‘Matrix Theory’

Matrix decompositions with sparsity constraints

Representing complex numbers as 2×2 matrices

Gilbert Strang’s lectures on Linear Algebra

Pages

Categories

Top Posts

Recent Posts

Recent Comments

Tag Cloud

Archives

Blog Stats

Artists

Blogs

Haskell

Math Blogs

MATLAB

Python

Robotics

Software

Symbolic Computation

Powered by FeedBurner

Meta

Follow “Rod Carvalho”

Rod Carvalho

Posts Tagged ‘Matrix Theory’

Matrix decompositions with sparsity constraints

Representing complex numbers as 2×2 matrices

Gilbert Strang’s lectures on Linear Algebra

Pages

Categories

Top Posts

Recent Posts

Recent Comments

Tag Cloud

Archives

Blog Stats

Artists

Blogs

Haskell

Math Blogs

MATLAB

Python

Robotics

Software

Symbolic Computation

Category Cloud

Powered by FeedBurner

Meta

Follow “Rod Carvalho”