1
vote
1answer
20 views

Is the adjacency matrix of every connected undirected graph irreducible? [on hold]

The adjacency matrix of every connected undirected graph is irreducible. Is this statement true?
0
votes
0answers
17 views

The lower bound of Cheeger Inequality as the degree goes to infinity

Consider an undirected graph $G(V,E)$ with adjacency matrix $A$ and define the graph Laplacian as \begin{equation} L = D - A \end{equation} where $D$ is a diagonal matrix such that $D(i,i) = d_i$. ...
0
votes
0answers
108 views

Matrix graph and irreducibility

\usepackage{multirow}!!!! How do I prove that if $A\in\mathbb C^{n\times n}$ is a matrix then it is irreducible if and only if its associated graph (defined as at Graph of a matrix) is strongly ...
1
vote
1answer
128 views

Graph of a matrix

How to define the graph of a square matrix $\mathbf{G}$ with real entries? I know that given a graph $\Gamma(V, E)$, one can define its adjacency matrix $\mathbf{A}$. But given a matrix $\mathbf{G}$ ...
0
votes
0answers
16 views

Matrix Representations of Chordal Graphs and Uses in Linear Algebra

Chordal graphs have the property of perfect elimination ordering. In Knuth's 2012 Christmas lecture ~1:12:10 he mentions that when the coefficients of a linear algebra problem can be written as a ...
0
votes
0answers
21 views

Eigen vectors of graph laplacians

I have been reading about spectral graph theory from Daniel A. Spielman's notes. Fiedler’s Nodal Domain Theorem from this note says that : Let $G = (V, E, w)$ be a weighted connected graph, and let ...
1
vote
1answer
42 views

$M_{R^n}$; how to derive $n$ for transitive closure?

When finding the transitive closure of a relation $R$, I convert $R$ into a boolean matrix $M_R$, and find the union between $M_R$ and its powers up to $n$. $$M_{R^*} = M_{R^1} \lor M_{R^2} \lor ...
0
votes
1answer
35 views

Calculating Adjacency Matrix

I'm having trouble understanding the concept, I know it is pretty simple but could someone help me out. Assume that I have the following: $V = \begin{bmatrix} 0&0&1 \\ 0&0&1 \\ ...
0
votes
1answer
42 views

Shortest distance matrix given an adjacency matrix?

If I have an adjacency matrix, how can I find a matrix that has the shortest distance between each pair of nodes? (distance matrix, but the nodes are not in a euclidean space) I'm trying to implement ...
1
vote
2answers
36 views

How do I find the adjacency matrix for the nodes of an n-dimensional finite grid?

I have an orthotopic grid, in n-dimensions (usually small ~<3), where each node is connected to it's orthogonal neighbours. The grid may be any number of nodes long, but is finite (and usually ...
1
vote
1answer
47 views

On Adjacency Matrix of a Graph with a Cut Vertex and a Bridge

Let $G$ be a graph. If $v_i$ (resp. $v_iv_j$) is a cut vertex (resp. a bridge) of $G$, what can you say about its adjacency matrix $A(G)$?
0
votes
1answer
37 views

Rank-one modification of graph Laplacian

Suppose I have a Laplacain matrix for a 3-node-path graph as follows $L=\left[\begin{array}{ccc} 1 & -1 & 0\\ -1 & 2 & -1\\ 0 & -1 & 1 \end{array}\right]$ Now, I want to ...
0
votes
1answer
22 views

How to describe symmetric nodes in a graph

For instance, in the path graph $P_4$, node $1$ and $4$ are symmetric, how to mathematically describe this in graph theory? And any algebraic properties related to this? Thanks!
1
vote
1answer
56 views

Permutation matrix and simple directed graph

I have some code that works with simple directed graphs, but it is kinda slow. So I converted it to use an adjacency matrix instead of keeping a list of pairs of nodes. The code finds the ...
1
vote
0answers
51 views

Prove that the minimum of row sums of a nonnegative symmetric matrix is preserved

Let $A$ be an $n\times n$ adjacency (nonnegative, irreducible and symmetric) matrix with zeros on the diagonal. Denote $i$-th row sum of $A^k$ as $r^{(k)}_i$, where $k\geq1$. I want to prove that if ...
1
vote
0answers
67 views

Adjacency matrix of directed graph

I am given adjacency matrix $A$ of directed graph. $A(x,y)$ counts the number of edges from $x$ to $y$. I want to show that if $A$ has constant outdegree $d$: (i) For any eigenvalue $\lambda$, we ...
1
vote
1answer
59 views

Principal EigenVector of an Adjacency matrix of an undirected graph

For an undirected graph, since the adjacency matrix will be symmetric, can we draw any relations between the principal eigenvector and the degree of nodes in the graph. Also can we do the same with ...
0
votes
1answer
50 views

How can one actually use Adjacency Matrix for understanding a graph?

I don't see any real reason why we would use an AM to represent a graph, beside visual appeal and ease. Generally, we would perform matrix operations on Matrices like |A|, Transpose and loads of other ...
1
vote
0answers
82 views

Area optimization: Packing rectangles inside rectangle

Background: I am scrambling to figure out the optimization algorithm to build sprite image, which is essentially a big container rectangular image, with multiple rectangular images. I have found an ...
2
votes
1answer
120 views

Finding characteristic polynomial of adjacency matrix

Short question im having a tad difficulty with. I'm trying to find the characteristic polynomial of a graph that is just a circle with n vertices and n edges. I think the adjacency matrix should ...
1
vote
1answer
79 views

Gauss Elimination for Colorability Problem

Consider the following system of linear equations modulo 2: $A.X + B.Y = Z, $ where $A$ is a non-singular(modulo 2) $n$ x $n$ boolean matrix, $B $ is $n$ x $m$ boolean matrix, $X$ is n-dimensional ...
1
vote
1answer
123 views

Uniqueness of doubly stochastic matrix descomposition

this is my first question in the site. Thanks in advance for all answers. It is well known that each bistochastic matrix can be represented as a convex combination of permutation matrices. I am ...
1
vote
1answer
102 views

Adjacency Matrices

Can someone explain adjacency matrix's in simple terms? I'm not grasping the material from the text at all, and can't solve the sample solutions provided.such as k2,k3 and the reverse. I understand ...
10
votes
1answer
211 views

From matrices to bipartite graphs

Assume $G(A,B)$ is a bipartite graph and assume $L(G)$ is the adjacency matrix of its line graph. define $$B=[3\text{I}+L(G)]^{-1}$$. Is it always the case that for each edge $e=(a,b)\in G$, we have: ...
5
votes
2answers
74 views

Do I influence myself more than my neighbors?

Consider relations between people is defined by a weighted symmetric undirected graph $W$, and $w_{ij}$ shows amount of weight $i$ has for $j$. Assume all weights are non-negative and less than $1$ ...
1
vote
1answer
51 views

Solving a Gaussian elimination problem.

I have been given a graph with n nodes. Now, I have to color every node of this graph by k colors, number from 0 to k-1. Now, there is a rule. For a node $x$ with adjacent nodes $y_1 , y_2, y_3, ...
0
votes
1answer
44 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 ...
0
votes
1answer
40 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 ...
0
votes
1answer
180 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 ...
1
vote
1answer
455 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 ...
3
votes
1answer
46 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. ...
0
votes
1answer
125 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 ...
2
votes
0answers
79 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 ...
0
votes
2answers
142 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 ...
1
vote
1answer
121 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 ...
0
votes
0answers
44 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 ...
0
votes
0answers
39 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 ...
2
votes
2answers
257 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 ...
1
vote
1answer
101 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): ...
1
vote
0answers
68 views

Threshold dense adjacency matrix

I have a dense, adjacency matrix (square, symmetric) representing a graph. I want to threshold that graph so that it only contains the largest weights (cells in the matrix), but is still fully ...
1
vote
1answer
60 views

Proof is needed for a lower bound of the maximal eigen-value of a non-negative, irreducible, integer matrix

$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 ...
1
vote
0answers
49 views

The meaning of the entries of eigenvectors of graphs

I would like an explanation to the meaning of the different entries of the eigenvectors of a graph. Furthermore, I'd be happy if anyone can spare an explanation for the meaning of the entries of any ...
1
vote
0answers
97 views

Extracting hitting times from the pseudoinverse of a Laplacian matrix for an undirected graph

Provided a pseudoinverted Laplacian matrix for an undirected graph $G$, how can I extract first passage and commute times between vertex pairs in $G$?
0
votes
0answers
60 views

Signed incidence matrix determinant and spanning tree

$G=(V,E)$ is a directed graph with $n$ vertices and $m$ edges, $n \geq 2$. $F \subseteq E$ and $|F| = n -1$. $Q$ is the $n \times m$ signed incidence matrix of $G$ over indeterminates $x_e$ with $e ...
2
votes
0answers
28 views

how the number of steps needed depends on the number of nodes and depends on the transmission range?

I run the consensus algorithm, and for each round k, we record the norm of the disagreement vector(|(|δ(k)|)|>〖10〗^(-6)). We stop, at a predefined value|(|δ(k)|)|>〖10〗^(-6) and we call this ...
0
votes
2answers
114 views

Adjacency matrix

Let $G$ be any simple and undirected graph. Let $A$ be the adjacency matrix of $G$. 1) Let $B$ be the number $\tfrac16\mathrm{tr}(A^3)$. What does $B$ count? That is $B$ counts the number of....? 2) ...
1
vote
0answers
26 views

Delocalization of eigenvectors in Expanding Graphs

Given an adjacency matrix A, can we say something about whether the eigenvectors corresponding to its highest(or second-highest) eigenvalues are delocalized ? By delocalization I mean that every ...
1
vote
1answer
147 views

How can i convert to the undirected matrix to an directed matrix?

Here A square matrix and first figure(AU) shows undirected connection graph and second one shows directed one.Assume that only i have Au metrix and how can i create Ad metrix from Au matrix in ...
1
vote
0answers
27 views

finding the decomposition of Laplacian matrix with position of zero elements unchanged

I'd like to know whether it's possible to find the decomposition of a Lapalacian matrix $A$ $B^TB = A$ where $B$ has the same dimension with $A$ and the position of zero elements in $B$ is the same ...
3
votes
2answers
59 views

Graphs with zero spectrum / nilpotent symmetric matrices

Is there a graph theoretic characterization of those graphs with zero spectrum? Alternatively, can one at least characterize all symmetric nilpotent (complex) matrices, so that one could recognize ...