2
votes
0answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
0
votes
1answer
26 views

Constructing an eigenvector for a certain matrix representing a graph with a perfect code

Let $A$ be a symmetric $(0,1)$-matrix whose row sum is $r.$ Suppose I have a $(0,1)$ vector $v$ such that $$Av = \vec{1} - v.$$ By taking the vector $$u = \vec{1} - (r+1)v$$ we see that $$Au = A ...
0
votes
0answers
11 views

compare magnitude of elements of Perron-Frobenious vector

Consider a nonnegative, primitive matrix $A=(a_{ij})_{n\times n}$ with positive diagonals. From the Perron-Frobenious theorem, the spectral radius $\rho(A)$ is an eigenvalue of $A$ and we have a ...
4
votes
1answer
40 views

What is the Laplacian Matrix used for?

You can turn graphs into several matrix forms depending on what data you want to focus on. Does the Laplacian form have any uses on its own, or does it need to be paired with other things as some ...
0
votes
0answers
28 views

Calculating Eigenvector Centrality & Betweenness Centrality formulas explained in simple terms

I'm currently working on a software application that has a function that analyses networks of people and the relationships between them. Two of the important variables we look at are Eigenvector ...
0
votes
0answers
14 views

What is the difference between closed and open subsets in reducibility of a graph

I've read somewhere the following sentence, the graph A is reducible to at two closed subsets. Is that different than just saying "A is reducible" ?? What is the difference between open and closed set ...
1
vote
0answers
48 views

Formula for position in an upper triangular matrix

I'm currently working on the Travelling Salesman's Problem in a computer science module. I have implemented some linear programming techniques using the software lp_solve. I've ended up with an upper ...
0
votes
2answers
41 views

Proving that irreducibility of a matrix implies strong connectedness of the graph [duplicate]

I have tried to prove that if a matrix $A\in\mathbb{C}^{n\times n}$ is such that there are no two sets $I,J\subseteq\{1,\dots,n\}$ that are disjoint, complementary, nonempty, and such that for all ...
0
votes
0answers
26 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$. ...
2
votes
2answers
207 views

Matrix graph and irreducibility

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 connected? Update: Seeing as ...
2
votes
1answer
148 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
18 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
26 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
47 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
50 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
100 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
56 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
75 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)$?
1
vote
1answer
40 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
24 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
78 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
55 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
99 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
124 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
95 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
122 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
151 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
80 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
149 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
109 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
221 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
75 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
56 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
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
3
votes
1answer
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. ...
0
votes
1answer
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 ...
2
votes
0answers
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
2answers
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 ...
1
vote
1answer
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): ...
1
vote
0answers
73 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
62 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 ...