[Math] How to express this in matrix notation (row-wise normalisation)

algebraic-graph-theorygraph theorymatricesnotation

My questions are:

How do I describe the row sum of a matrix?
How do I describe the number of non-zero elements per row of a matrix in matrix notation?
How do I divide a vector elementwise?

To give you context:

I have a graph $(V,E,\mathbf{W})$ where $\mathbf{W} \in \mathbb{R}^{n\times n}$ is a weight matrix describing the edges $E$ connecting vertices $V$. I also have a vector $\mathbf{c} \in \mathbb{R}^{n \times 1}$ containing values at each edge.

The elements in $\mathbf{c}$ are updated like this:

$c_i(t+1) = \frac{1}{|V_i|} \sum_{j \in V_i} w_{ij} c_j(t)$

where $V_i$ is the set of neighbours of vertex $i$ and $|V_i|$ denotes the number of nodes in the set. I would like to express this using matrix notation.

Best Answer

Let $\mathbf{A}$ be the adjaciency matrix of the unweighted equivalent to $G$ and $\mathbf{D}$ is the corresponding diagonal degree matrix (the sum of all outgoing connections of a node, also the row-sum). $\mathbf{c}(t+1)$ can then be expressed by:

$\mathbf{c}(t+1) = \mathbf{D}^{-1} \mathbf{W} \mathbf{c}(t) $

Related Solutions

[Math] ny standard notation for specifying dimension of a matrix after the matrix symbol

Sometimes your notation is used. The problem of the ambiguity of $X_{m \times n}^T$ comes from the wrong usage. There is no such thing as $X_{m \times n}^T$. Instead, there is $X_{m \times n}$ and there is $X^T$. Combining these two will give you either $(X_{m \times n})^T$ or $(X^T)_{m \times n}$, and removing the parentheses implies that $*_{* \times *}$ and $*^T$ commute (like, for example, $X^{-T} = (X^{-1})^T = (X^T)^{-1}$), which is wrong.

However, I see very little, if any, practical usage in this kind of typesetting. More or less standard way is $X \in \mathbb{R}^{m \times n}$ or $X \in M_{m \times n}(\mathbb{R})$, and then you just use $X$. Writing dimensions in the formulas might make sense at the very beginning of learning this stuff, but not for long, and in this case, parentheses also make a lot of sense.

For anything more advanced, let me give you an example: would you, in a similar fashion, write

$$x_\text{even} + y_\text{odd} = z_\text{odd}?$$

Properties of the objects usually unnecessarily clutter your formulas, and are far better to be declared before the first use, instead of all the time. IMO, of course.

[Math] How to find the adjacency matrix for the nodes of an n-dimensional finite grid

Ok, so I worked it out, after a lot of trial and error. Here is the code that I'm using in python. If there is a better way of doing this, I would happily accept another answer.

import numpy as np

def _unserialise_coordinate(serial, spacing):
    coord = []
    for i in range(len(spacing)):
        coord.append(int(np.floor(serial/spacing[i])))
        serial = int(serial % spacing[i])

    return(coord)

def _serialise_coordinate(coord, spacing):
    return(np.dot(coord, spacing))

def _generate_adjacency_matrix(grid_dimensions):
    """Generate an adjacency matrix for nodes of an orthotopic grid with
    dimensions given by grid_dimensions
    """
    n_centres = np.prod(grid_dimensions)

    adjacency = np.zeros((n_centres, n_centres))

    spacing = [int(np.prod(grid_dimensions[(k+1):])) for k in range(len(grid_dimensions))]

    for i in range(n_centres):
        coord = _unserialise_coordinate(i, spacing)
        neighbours = []
        for d in range(len(grid_dimensions)):
            if coord[d] > 0:
                down = coord.copy()
                down[d] -= 1
                neighbours.append(down)
            if coord[d] < (grid_dimensions[d] - 1):
                up = coord.copy()
                up[d] += 1
                neighbours.append(up)

        for neighbour in neighbours:
            serial = _serialise_coordinate(neighbour, spacing)
            adjacency[i,serial] = 1

    return(adjacency)

Best Answer

Related Solutions

[Math] ny standard notation for specifying dimension of a matrix after the matrix symbol

[Math] How to find the adjacency matrix for the nodes of an n-dimensional finite grid

Related Question