Tagged Questions
1
vote
1answer
41 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
39 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
36 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
30 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
21 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 ...
1
vote
2answers
63 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
18 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
73 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
23 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
43 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 ...
2
votes
2answers
30 views
Prove that a strongly connected digraph has an irreducible adjacency matrix?
In our homework we are asked to prove the above fact. If anybody would be willing to give advice I would be most thankful.
Thanks
0
votes
1answer
64 views
Prove $MM^t=A+kI$ for matrices associated to graphs
How can I prove that $MM^t=A+kI$ for incidence matrix $M$ and adjacency matrix $A$ of a $k$-regular graph with $n$ vertices?
It is easy to see that $MM^t$ is an $n\times n$-matrix (like $A$), ...
0
votes
0answers
42 views
Nilpotency of the adjacency matrix of a directed tree network
Say I have a directed network that is organized in a tree, with all connections going downstream (genealogically). By that I mean that there is one root node connected to $c_{00}$ child nodes, and ...
2
votes
0answers
81 views
Low-rank approximation to the Graph Laplacian matrix of a regular grid.
As mentioned in the title, does anybody know any methods of efficient low-rank approximation $LL^T$ to the Graph Laplacian matrix $A$ corresponding to a square lattice? (except PCA)
4
votes
1answer
121 views
What is the difference between first and second right eigenvectors of a row stochastic matrix and their meaning?
In an $n\times n$ non negative row stochastic matrix (rows sum up to 1).
The entries of the stochastic matrix I have represent directed links between countries.
Why is the first right eigenvector a ...
1
vote
3answers
42 views
Graph of a matrix and a positive power for the the matrix
A graph has a path from node $j$ to node $i$ if and only if its adjacency matrix has a positive element $(i,j)$ of $A^k$ for some integer $k.$
A proof for this statement will be highly appreciated.
1
vote
2answers
89 views
A multiple-part question about interpreting powers of the adjacency matrix of a graph
Suppose that we have a group of six people, each of whom owns a communication device. We define a $6\times 6$ matrix $A$ as follows: For $1\le i\le 6$, let $a_{ii}=0$; and for $i\ne j$, ...
-1
votes
2answers
90 views
0
votes
0answers
34 views
Name of the inverse of a reduced node-arc incidence matrix
So I basically have a directed incidence matrix 'A' and its inverse 's' has been labelled as "sensitivity matrix"; is that right? {the label is a comment in a matlab program}
Also, it's been said ...
0
votes
2answers
88 views
How to test if a graph is fully connected and finding isolated graphs from an adjacency matrix
I have large sparse adjacency matrices that may or maybe not be fully connected. I would like to find out if a matrix is fully connected or not and if it is, which groups of nodes belong to a ...
0
votes
0answers
37 views
What is the name of the matrices which reorder edges in an adjancency so that they are closer to the diagonal? (modularity/structure)
I have seen adjacency matrices presented where the edges formed box like formations along the diagonal (not block matrices). This helped view the modularity and community structure of the group of ...
0
votes
2answers
145 views
Easiest way to determine all disconnected sets from a graph?
Suppose that I have a un-directed graph of nodes and edges, I would like to know all sets of nodes that do not connect with any other nodes in the graph.
Here is a concrete example to help you ...
6
votes
1answer
299 views
When does the adjacency or incidence matrix of a graph have consecutive ones property?
Given a graph, what are some sufficient (and necessary) conditions to tell if its adjacency matrix has the consecutive ones property?
Similar question for its incidence matrix?
Note that a ...
6
votes
2answers
123 views
Graphs with commuting adjacency matrices
Let A and B be adjacency matrix of two undirected simple graphs. Can we assign some combinatorial interpretations to this pair of graphs if A and B commute?
0
votes
1answer
110 views
Adjacency matrices needed for common graphs
I'm making a program which requires adjacency matrices of undirected graphs. In particular, I'd like the adjacency matrices for the graphs in this wiki link:
...
2
votes
0answers
22 views
Quantities measuring the sparseness of a graph and of a matrix?
What are some quantities often used to measure the sparseness of a graph?
For example, in a graph, with the number of vertices fixed, the
smaller the maximum degree is, the more sparse the graph is. ...
0
votes
0answers
46 views
Abbreviations in Combinatorial Graph/Matrix theory
I'm getting started with research in combinatorics. I have come across a reference that uses a great deal of abbreviations. I was able to figure most of them out but there are a few that I can find.
...
1
vote
1answer
89 views
Strongly connected graph associated with a matrix
This type of matrices $L$ is called Leslie type matrices in Population dynamics:
$$L = \begin{pmatrix} f_{11} & f_{12} & f_{13} & \dotsm & f_{1,i-1} & f_{1,i}& \dotsm & ...
1
vote
1answer
747 views
Graph Theory Shortest Path Problem via Matrix Operations in MatLab
Here is something that has been getting the best of me for past few days. Hopefully someone can point me get in the right direction.
I have a graph G, and I need ...
3
votes
3answers
169 views
When a directed graph is represented in matrix form, what is the interpretation of the inverse of this matrix?
Let $G$ be a directed (unweighted) graph with $n$ nodes. We can represent $G$ with an $n \times n$ binary matrix $A$, with $A_{ij} = 1$ if there is an edge $i \to j$ and $A_{ij} = 0$ otherwise.
...
2
votes
1answer
74 views
Possible relation between spectra bounds of two matrices
A Laplacian matrix $L\in\mathbb{R}^{n\times n}$, is a symmetric matrix with entries, \begin{equation}
l_{ij}=\begin{cases} 1=\sum_{i,~ i\neq j} w_{ij} &\mbox{if } i=j \\
-w_{ij} & ...
1
vote
0answers
41 views
how to calculate the spectrum and inertia of sign pattern matrix?
I want to know how to calculate the spectrum and inertia of sign pattern matrix, how to use Nilpotent-Jacobian method to solve the problem about determinating spectrally arbitrary and inertially ...
0
votes
1answer
199 views
Calculating powers of 2 on a 2D grid without factoring.
Consider the following 2D infinitely large grid where the dots represent infinity:
...
1
vote
1answer
250 views
How to prove that a matrix is positive definite?
Let $L$ be a Laplacian matrix of a strong connected and balanced directed
graph. Define
$$
L^{s}=\frac{1}{2}\left( L+L^{T}\right) .$$
Let $D$ be a diagonal matrix with
$$
D=\begin{bmatrix}
d_{1} & ...
0
votes
1answer
43 views
Reading a Laplacian Matrix and its labeled graph?
How can the following labeled graph be extracted from the Laplacian Matrix below and viceversa?
I had a look at this great conversation but it is already too advanced for me.
2
votes
0answers
167 views
Orbits of adjacency matrices under conjugation by permutation matrices.
(Disclaimer: I am new here, so be patient with my mistakes, but I welcome corrections, advice or comments.)
I am interested in if anyone knows of ways of characterizing the orbits of an adjacency ...
6
votes
3answers
665 views
Significance of eigenvalue
When I represent a graph with a matrix and calculate its eigenvalues what does it signify? I mean, what will spectral analysis of a graph tell me?
1
vote
0answers
239 views
Transitive reduction: calculating “relation composition” of matrices?
I have graphs represented by matrices. For example,
$\begin{matrix} 0&0&0\\1&0&0\\1&1&0\end{matrix}$
Produces this graph:
The graphs are supposed to be transitive, i.e. ...
0
votes
1answer
95 views
Random Walks and Jumps
I am trying to understand why Random Walks' and Random Jumps', on a graph, transition matrix are also stochastic matrix.
A stochastic matrix is a matrix the values of each row add up to 1 and no ...
1
vote
0answers
86 views
Finding All Spanning Tree
Given a regular directed graph $G(n,d)$, where $d$ is the total of in-degree dan out-degree and $n$ is the number of vertices (so that $G(n,d)$ has $dn$ edges). Let $A \in M_n (\{0,1\})$ matrix which ...
1
vote
1answer
224 views
Transition matrix
I have a directed graph $G_1$. I extract its transition matrix $T_1$.
Now I also have directed graph $G_2$, which is equal to $G_1$ with inverted edges.
If I get its transition matrix $T_2$, what is ...
2
votes
2answers
172 views
Given any polynomial p(x) over Z, can one construct a graph with characteristic polynomial p(x)?
Given any polynomial $p(x)$ over $\mathbb{Z}$, can one construct a graph with characteristic polynomial $p(x)$? [Edit: Title question added to post.}
Further questions include:
Are there classes of ...
1
vote
2answers
265 views
Counting paths of a variable length on a directed graph
If I've been given a directed Graph $G = (V,E)$ and its adjacency matrix $A$. How do I calculate how many (directed) paths do exist from one specific node to another (specific) one?
In general ...
1
vote
1answer
225 views
Graph Invariants (covering design)
I am not a mathematician so please take that into consideration when formulating your answers.
Technically 2 graphs are NOT isomorphic if any one of the countless graph invariants (i.e. vertices, ...
1
vote
1answer
227 views
eigen decomposition of an interesting matrix (general case)
Lets define:
$U=\left \{ u_j\right \} , 1 \leq j\leq N= b^{L},$ the set of all different sequences of length $L$ where each element of the sequence can be an integer in $\left \{ 0, 1, .., b-1 ...
4
votes
1answer
298 views
eigen decomposition of an interesting matrix
Lets define:
$U=\left \{ u_j\right \} , 1 \leq j\leq N= 2^{L},$ the set of all different binary sequences of length $L$.
$V=\left \{ v_i\right \} , 1 \leq i\leq M=\binom{L}{k}2^{k},$ the set of ...
5
votes
1answer
305 views
Rank of an interesting matrix
Lets define:
$U=\left \{ u_j\right \} , 1 \leq j\leq N= 2^{L},$ the set of all different binary sequences of length $L$.
$V=\left \{ v_i\right \} , 1 \leq i\leq M=\binom{L}{k}2^{k},$ the set of ...
1
vote
1answer
185 views
Rank of a graph matrix
$G$ is a bipartite graph with $2m$ nodes on the left $(u_0..u_{2m-1})$, and $2^{m}$ nodes on the right $(v_0..v_{2^{m}-1})$.
There is an edge (connection) between $u_i$ and $v_j$ iff $(i+1)$'th ...
4
votes
2answers
298 views
Knowledge about Graph Spectral Theory and correlation between a graph Weighted Adjacency matrix and its eigenvalues
I know that this question is some sort of bridge between Informatics and Mathematics, not knowing the best place where to post this question, I opted for this place because of the type of answer I ...
5
votes
2answers
534 views
connection between graphs and the eigenvectors of their matrix representation
I am trying to learn graph theory and the linear algebra used to analyse graphs. The texts I have read through have lots of lemmas and theorems proved. The proofs are convincing but I fail to see the ...
