# Tagged Questions

23 views

### Counting symmetric binary matrices with constant line-sum

I'm trying to count, as the title suggests, symmetric matrices with entries $0$ or $1$ and constant line-sum $k$. ($0 \leq k \leq n$). If you start listing the number of these on a table you'll get a ...
25 views

### Irreducible matrix equivalent connectedness of matrix graph?

If a matrix is irreducible, based on the following definition A matrix is reducible if there are two disjoint sets of indexes $I,J$ with $|I|=\mu$, $|J|=\nu$, $\mu+\nu=n$ such that for every ...
38 views

### Checking connectivity of adjacency matrix

What do you think is the most efficient algorithm for checking whether a graph represented by an adjacency matrix is connected? In my case I'm also given the weights of each edge. There is another ...
26 views

50 views

54 views

### Are these equivalent representations (labelled graph and adjacency matrix)?

This is an example from Wikipedia's page on adjacency matrices, which from the site's format seems to be suggesting equivalence between the simple diagram below, left, and the abstractly represented ...
42 views

### Can this famous theorem extended to the weighted undirected graphs?

There is well-known bound on the largest eigenvalue of graphs that says $$\sqrt{d_{max}}\leq \lambda_{max}$$. Is it also true for weighted graphs? (Where as usual, the degree of a vertex in a weighted ...
265 views

### Constructing a graph from a degree sequence

Let's say I'm given several degree sequences like {4,3,3,2,2} {3,3,3,3} {5,3,3,2,2,1} I can find the number of edges using the handshaking lemma But how do I construct a graph just given these ...
900 views

### How to construct the graph from an adjacency matrix?

I have the following adjacency matrix: a b c d a [0, 0, 1, 1] b [0, 0, 1, 0] c [1, 1, 0, 1] d [1, 1, 1, 0] How do I draw the graph, given its adjacency ...
53 views

### If $A$ is the adjacency matrix of a graph, why does the $(i,j)$ entry of $A^n$ give the number of $n$-step walks from $i$th vertex to $j$th vertex?

Let $A$ be the adjacency matrix of some directed graph with $m$ vertices labeled as $v_1, v_2, \ldots, v_m$. So here $A_{ij} = 1$ if there is an edge from $v_i$ to $v_j$, and $A_{ij} = 0$ otherwise. ...
163 views

### How to determine if a sparse matrix is structurally smmetric

Say you have a sparse matrix in CSC or CSR format (or whatever format is suitable for this to work) and all you know are it's dimensions: $n$, $m$ and $nz$, and the data in the structure. You are told ...
85 views

### Does a matrix represent a bijection

We have a square binary matrix that represents a connection from rows to columns. Is there a way to tell if a bijection exists (other than checking for all possible bijections and iterating through ...
194 views

### Test for acyclic graph property based on adjacency matrix

I am trying to solve a problem that I have but I lack the theoretical knowledge that might be necessary to solve it. I have a directed graph encoded as an adjacency matrix. Is it possible to test ...
135 views

### How to express this in matrix notation (row-wise normalisation)

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 ...
53 views

### Spectral moments of signless Laplacians through eigenvalues of the line graph?

For a simple graph G, the following relationships hold: $$RR^T=\Delta+A$$ and $$R^TR=2I+A_{L(G)}$$ where R is the incidence matrix, A is the adjacency matrix, I is the identity matrix, $A_{L(G)}$ is ...
41 views

### When random walk Markov matrix of the graph is normal?

I'm considering random walk on undirected graph $G$. At every time step, walker moves to a random neighbour, with all neighbours being equally likely. With adjacency matrix $A$ the random walk Markov ...
288 views

### The second largest eigenvalue for Perron-Frobenius matrix

The Perron-Frobenius theorem is about the largest eigenvalue and eigenvector of a non-negative (irreducible) matrix. My question: Is there any estimation of the difference between the first and ...
109 views

### Minimal spectral radius of a primitive matrix

Given the set of all primitive matrices of dimensions $m$ by $m$ that are non-negative and integer - which one is the matrix with the minimal spectral radius? Edit (according to the first comment): ...
$A$ is a non-negative, integer, irreducible, $m$ by $m$ matrix. It is well known (Perron-Frobenius) that $A$ has a positive eigen value (denote it by $\lambda$) with a positive eigen vector ($x$). It ...