0
$\begingroup$

I've looked hard and failed to find any convincingly standard algebraic notation for such. I have a specific problem in mind. It is the transformation of this matrix:

$\mathrm{W} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0.25 & 0 \\ 0 & 0.75 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} $

into this one:

$\mathrm{A} = \begin{bmatrix} 1 & 0 \\ -0.25 & 0.25 \\ -0.75 & 0.75 \\ 0 &-1 \\ \end{bmatrix} $

It's rather easy to see how to do that column by column, basically:

$a_{i,j} = w_{i,j} - w_{i,j+1}$

and I can write code do that but what I'm look for is a nice algebraic nomenclature for the operation, ideally in a standard matrix notation such that I might write:

$\mathrm{A} = f(\mathrm{W})$

and I could write the function f algebraically somehow. I can invent a notation easily enough, for example:

$\mathrm{A} = \mathrm{W}>>1 - \mathrm{W}<<1$

where:

$>>$ is a right shift operator which shifts each column one to right losing the right most column and reducing the number of columns by 1.

$<<$ is a left shift operation which shifts each column one to the left losing the first column and reducing the number of columns by 1.

But I made that up. And of course we can work on transposes and use row operators if they exist instead. By quest here is for the most standard, widely understood and used algebraic notation if it exists, and ideally a reference I could cite that documents it. I've failed to find any such thing.

$\endgroup$
  • $\begingroup$ Yes! Note that the function which sends $W\rightarrow A$ is linear. Say you have the equation $WM=A$. What must $M$ be to make this equation true? This would allow you to write the function simply as $f(W)=WM$ $\endgroup$ – rikhavshah May 29 '18 at 2:50
  • 1
    $\begingroup$ Food for thought, thanks. But yes what would $\mathrm{M}$ be? I find it easier to replicate the truncation (shift)/resizing operations I noted above by specifying M: I can replicate left truncation with $\mathrm{M}=\begin{bmatrix} 0 & 0 \\ 1 & 0 \\ 0 & 1 \\ \end{bmatrix}$ and a right truncation with: $\mathrm{M}=\begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \\ \end{bmatrix}$ Which seems like a combination of the identity matrix and a null row. But what’s the nomenclature for that, how do we write $\mathrm{M}$ generically? $\endgroup$ – Bernd Wechner May 29 '18 at 3:21
1
$\begingroup$

One potential answer is to use colon notation $$ f(W) = W(:,\text{1:end-1}) - W(:,\text{2:end}) $$ It is well-known within the numeric linear algebra community; see for example Golub & Van Loan (2013).

$\endgroup$
1
$\begingroup$

This is simply the linear transformation $$A=WP$$ where $$ P = \begin{bmatrix} \,\,\,1 & \,\,\,0 \\ -1 & \,\,\,1 \\ \,\,\,0 & -1 \\ \end{bmatrix} $$

Update

Let's consider the case $m=4$, and the permutation matrix with ones on the first sub-diagonal $$ B = \begin{bmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix}\in{\mathbb R}^{m\times m} $$

Then $B^m=I,\,$ and the product $$ W(I-B) = \big[\,A\,\,c\,\big] $$ yields the desired $A$ matrix augmented by an extra column $(c)$ which contains the difference of the last & first columns of $W$. This is the circulant extension of your differencing algorithm.

$\endgroup$
  • $\begingroup$ That great! I love it. But is there a way to express $\mathrm{P}$ in generic terms as I have $\mathrm{L}$ and $\mathrm{R}$? As in can this generalise for any $n \times m$ matrix to convert it to a $n \times m-1$ matrix with columns that are the difference of columns in the first? $\endgroup$ – Bernd Wechner May 29 '18 at 5:52
  • $\begingroup$ @BerndWechner This answer has been updated to make it more generic, regarding the size of the matrices. $\endgroup$ – greg May 29 '18 at 7:59
  • $\begingroup$ Interesting. Thanks for your creative thinking. I'll experiment with this tomorrow out of interest. But I'd rather have a way of saying A=f(W) rather than finding it embedded in a larger matrix. I'm on a (re)learning curve, as it's been decades since I did a lot of matrix work (pre PC era) and so am revisiting the algebra of matrices. Matrices are distributive for example and so my answer below may simplify to W(R-L). $\endgroup$ – Bernd Wechner May 29 '18 at 11:01
  • $\begingroup$ @BerndWechner I think we've both come up with the same solution, since $$W(R-L)=W(I-B)R$$ I just think the definition of $R$ will make it awkward to implement. Whereas most computer languages have a simple syntax for extracting a sub-matrix. $\endgroup$ – greg May 30 '18 at 16:21
1
$\begingroup$

Thanks to rikhavshah's hint I think I've nailed something I'm satisfied with, as follows:

$\mathrm{A} = \mathrm{W}\mathrm{R} - \mathrm{W}\mathrm{L}$

where:

$\mathrm{W}$ is an $n \times m$ matrix

$\mathrm{A}$ is an $n \times m-1$ matrix being the differences between adjacent columns in $\mathrm{W}$

$\mathrm{R} = \begin{bmatrix} \mathrm{I}_{m-1} \\ 0_{1,m-1} \end{bmatrix} $ is an $m \times m-1$ right truncating matrix

$\mathrm{L} = \begin{bmatrix} 0_{1,m-1}\\ \mathrm{I}_{m-1} \end{bmatrix} $ is an $m \times m-1$ left truncating matrix

and so a worked example for the specific matrices in the question:

$ \begin{align*} \mathrm{A} &= \mathrm{W} \mathrm{R} - \mathrm{W} \mathrm{L} \\&= \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0.25 & 0 \\ 0 & 0.75 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{bmatrix} - \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0.25 & 0 \\ 0 & 0.75 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} 0 & 0 \\ 1 & 0 \\ 0 & 1 \end{bmatrix} \\&= \begin{bmatrix} 1 & 0 \\ 0 & 0.25 \\ 0 & 0.75 \\ 0 & 0 \\ \end{bmatrix} - \begin{bmatrix} 0 & 0 \\ 0.25 & 0 \\ 0.75 & 0 \\ 0 & 1 \\ \end{bmatrix} \\&= \begin{bmatrix} 1 & 0 \\ -0.25 & 0.25 \\ -0.75 & 0.75 \\ 0 & -1 \\ \end{bmatrix} \end{align*}$

which uses only standard notation from:

which I find standard enough with references available for the naive reader.

If there is a better option I'm all ears but this one seems the best so far!

UPDATE:

This can simplify further to:

$\mathrm{A} = \mathrm{W}\boldsymbol\Delta$

Where: $\boldsymbol\Delta = \begin{bmatrix} \mathrm{I}_{m-1} \\ 0_{1,m-1} \end{bmatrix} - \begin{bmatrix} 0_{1,m-1} \\ \mathrm{I}_{m-1} \end{bmatrix}$

Which is easily the most elegant solution to date. Defining on generic multiplier for the conversion. We can think of $\boldsymbol\Delta$ as a differencing matrix methinks which creates for any matrix a new on which has one fewer columns and each column is the difference between two adjacent columns in the original.

$\endgroup$
  • $\begingroup$ Can I ask why you need 'standard notation'? Notation varies depending on the field of math you're in; it would be perfectly standard to define your own `column difference' matrix $M$ such that $A=WM$. $\endgroup$ – rikhavshah May 29 '18 at 6:14
  • $\begingroup$ "need" would be an exaggeration. "desire" is a better word. I desire it simply because I'm not very deeply enmeshed in any field right now and not writing for one, so much as trying to understand something and writing it up for lay readers as well some time, plus I simply prefer standards to document or author specific conventions or even field specific ones. Just a preference is all. The problem space I'm looking at however should take any matrix $W$ to produce $A$, of any dimension and any content - to wit a desire to describe the transformation tersely and in standard notation. $\endgroup$ – Bernd Wechner May 29 '18 at 6:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.