# Tagged Questions

15 views

### Prove one of the eigenvector entries has the smallest magnitude

Let $L\in \mathbb{R}^{n \times n}$ be the Laplacian matrix of a simple undirected graph and $D_i$ be the same size matrix with $i$th diagonal element $1$. Denote the smallest eigenvalue of $L+D_i$ as ...
28 views

### Kronecker product and the vec operator: confusion on proof of vec(AXB) = (transpose(B) ⊗ A) vec(X)

I was reading up on Kronecker products and vec operator from couple of sources and landed on the equation: vec(AXB) = (transpose(B) ⊗ A) vec(X) suppose ...
59 views

### Determine cycle from adjacency matrix

Is there a way/algorithm to determine if there is a cycle in a graph if I only have the adjacency matrix and can not visualize the graph?
27 views

### Tightest upper bound for $\sum_j g_{ij}$ of an adjacency matrix of a graph

If I have an adjacency matrix of a graph $G$ (i.e. $g_{ij}=1$ if $i$ and $j$ are connected and $g_{ij}=0$ if not. $g_{ii}=0$), is there any tighter upper bound on $\sum_{j} g_{ij}$ than just $n-1$ ...
61 views

### Measuring the entropy of a graph representing a transition probability matrix of a first order markov chain

There's a research project i'm currently working on which requires me to analyze various aspects of "worlds" represented by transition probability matrices, where the nodes represent objects in the ...
59 views

### Sparse matrix algorithms involving data-driven or random access / walk

I am looking for some well-known algorithms in which sparse matrix elements are accessed in a non-structured way, i.e. row/column depends on a value of another (sparse) matrix/vector element or some ...
141 views

### Tree Traversal - Simple Puzzle type Issue.

This is a puzzle like question,based on Fibonacci like structure of the tree. Actually it is a short question with out any complex concepts. It appears bit big,since I have added explanations with ...
31 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 ...
28 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 ...
59 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 ...
40 views

### Checking the correctness of the adjacency matrix for the given graph

I found the adjacency matrix for this graph; it is shown next to it. Is it correct?
27 views

60 views

65 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 ...
44 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 ...
313 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 ...
1k 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 ...
59 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. ...
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 ...