0
votes
0answers
20 views

Matrix norm to compare two graphs

I have the adjacency matrices of two undirected graphs. I want to measure how different the two matrices are in terms of the linkage. Both matrices have the same number of nodes, but they differ in ...
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 ...
3
votes
0answers
40 views

maximizing the inverse degree in a graph

The inverse degree in the graph $G$ is defined as \begin{align*} r(G) = \sum_{i=1}^N \frac{1}{d_i}, \end{align*} where $d_i$ is the degree of node (vertex) $i$. Is the connected graph with maximum ...
4
votes
1answer
112 views

Bipartite graph matching like problem.

Let $A=\{a_1,a_2, ..., a_n \}$ and $B=\{b_1,...,b_m\}$ be finite sets. Also $A_1,...,A_k\subset A$ are covering of $A$ and $B_1,...,B_t\subset B$ are covering of $B$. Let $V$ be a set of pairs of ...
1
vote
1answer
46 views

Solution of $B^{\text{T}}B=Q$ for B?

Let $B$ be an $m$ by $n$ matrix whose entries are either 1 or 0 (it is an undirected incidence matrix). Given the $n$ by $n$ matrix $Q$, defined by $B^{\text{T}}B=Q$, is it possible to solve for $B$? ...
2
votes
0answers
41 views

Heat equation on a graph Laplacian

I would like to start with considering the time-dependent heat equation on a connected graph. To start, I will need to model it respect to time discretization. I mean I have to write something like: ...
1
vote
0answers
29 views

Finding the adjacency matrix for any given quiver and some collection of words.

For a directed graph (quiver) $Q$ with $n$ vertices and without multiple arrows, we have the adjacency matrix $A$, in which $A(i,j)=1$, if there is an arrow from $i$ to $j$, and $0$ elsewhere. This ...
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 ...
1
vote
3answers
113 views

Choosing good textbooks in linear algebra, analysis and graph theory

I need some advices to choose good undergraduate textbooks in LINEAR ALGEBRA, ANALYSIS and GRAPH THEORY. I found: Gilbert Strang // Introduction to Linear Algebra - Welleslay Cambridge Press (2009) ...
0
votes
2answers
37 views

Interpretation of Powers of matrix

Suppose there is a square binary matrix (Adjacency matrix of a graph), $A$. I got that, the matrices, $A^2$ and $A^3$ are distinct but the set of eigenvalues are same for $A^2$ and $A^3$. It is to be ...
0
votes
1answer
72 views

A question about rational number.

Denote $M$ as a $m\times n$ matrix whose components are all nonnegative integers (actually 0 or 1) and $1$ as the $m$ dimensional vector $(1,1,\cdots,1)$. Show that: There is a vector $x_0$ ...
0
votes
0answers
24 views

mean number of links in adjacency matrix

I have converted from an individual-level adjacency matrix to one for clusters and I am trying to show mathematically how I programmed up determining the mean number of inter-cluster links. I am not ...
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
1answer
31 views

Preferential Attachment and salton similatiy in directed networks

Preferential Attachment similarity between two nodes in an undirected graph is the degree of the first node multiplied by the degree of the second node. But what about directed graphs? Which degree ...
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
0answers
43 views

Distance matrix of connected graph always invertible?

I know there's a question elsewhere about distance matrix for points on Euclidean plane, but I'm not sure if that one was relevant. Anyway, given a connected (simple) graph G with $n$ vertices ...
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
56 views

Find eigenvalues from a given relation.

This is a simple problem of linear algebra. One without knowing graph theory may solve it. I am missing a small easy logic. Description: Let $G$ be a graph with $n$ vertices and $G^c$ is its ...
3
votes
1answer
58 views

Proof Technique: Linear Independence - What makes the technique work in general?

Reading the book on Graph theory written by Bondy and Murty (Springer), they present the following proof technique (Linear Indepence) to use when the combinatorial approach fail. My questions are: ...
0
votes
0answers
31 views

Computing an element of Moore-Penrose pseudoinverse of a large sparse matrix

I am computing resistance between two points in a network. To do this I compute the Laplace matrix and then take a Moore-Penrose pseudoinverse. However, I am really only interested in the resistance ...
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 ...
0
votes
1answer
43 views

psittacism: Fundamental Theory of Time

This question is in reference to the programming question found here. What method of approach should I be thinking of if I have a list of lectures A, B, and C, and discussions D, E, and F, that are ...
0
votes
0answers
33 views

Adjacency matrix of strongly connected digraph

If I have $A$ the adjacency of a strongly connected digraph, I want to show: For $\lambda$ satisfying $Ae= \lambda e$ for nonegative $e$, I want to show for any eigenvector (could be negative), the ...
0
votes
0answers
48 views

All simple cycles of a simple undirected graph size n

Given a hollow 2x2 weighted adjacency matrix with nonnegative integer elements e.g.: \begin{bmatrix} 0 & 4 \\ 7 & 0 \end{bmatrix} a matrix basis I want for 2x2 matrices is $\begin{bmatrix} 0 ...
1
vote
1answer
125 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 ...
1
vote
2answers
43 views

Number of triangles in a Graph/Network

Given An undirected graph/Network, and its adjacency matrix A, and 1 (A column vector with all elements as 1). How do we represent the problem of finding the number of triangles in the network ...
1
vote
1answer
37 views

Determinants, traces and isomporphism of graphs

Question Prove that if A,B are adjacency matrices of two graphs, and their traces or determinants are not equal then the graphs are not isomorphic. Thoughts I know that 2 graph are isomorphic iff ...
2
votes
1answer
47 views

A question about the interlacing of symmetric matrices (graph interlacing)

Reading the paper of Haemers on graph interlacing I came across the following question. Let $A$ be a real symmetric matrix partitioned into $m \times m$ blocks and suppose $B$ is a $m \times m$ ...
0
votes
1answer
40 views

Vertices, Edges and Line Segment intersection points

So, I have a bunch of graph edges defined by start and end vertices i.e. edge = (startVertex, EndVertex). No coordinates i.e x or y points provided. How do I ...
1
vote
1answer
50 views

Characterize graph by its connectivity matrix

Let $A$ be an $n\times n$ symmetric matrix, all of whose entries are $1$ or zero. Such a matrix is associated with an undirected graph $G$ with $n$ nodes, in which there is an edge between ...
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
votes
1answer
67 views

find a common plane which contains two points (NP hard?)

In this problem the coordinates of 4 points are given. $p_{0}=(x_{0},y_{0},z_{0})$, $p_{1}=(x_{1},y_{1},z_{1})$, $p_{2}=(x_{2},y_{2},z_{2})$ and $p_{3}=(x_{3},y_{3},z_{3})$ I need to find the ...
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
56 views

Calculate a determinant related to permutation matrix

Let $ M$ be a permutation $n \times n $ matrix and $[\lambda_1,\lambda_2, \ldots,\lambda_n]$ be the cycle type of the corresponding permutation, i.e. $ \lambda_i$ is the number of cycles of the ...
11
votes
1answer
914 views

Showing that a matrix is positive (semi-)definite

Let $G = (V,E)$ be a connected graph and $T$ one of its spanning trees. Let $w \in[0,1]^{|V|-1}$ be a weight for the spanning tree, i.e. we assign to each of the spanning tree's edges a number in ...
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
70 views

Finding the “middle 2” of four lines

This may seem like an overly abstract problem, but it's the best generalization I could make of a specific problem I'm trying to tackle. This problem works in 2-dimensional Euclidean space. A ...
0
votes
2answers
377 views

Rank of adjacency matrix vs rank of graph Laplacian

What is the relation between rank of the adjacency matrix of a graph and rank of the corresponding graph Laplacian matrix?
1
vote
1answer
61 views

Find self-avoiding-filling-polygon represented by system of linear equations

In Euclidean graph where each vertex is a point on the $2D$ plane, so the weight of each edge is the Euclidean distance between the vertices. I want to find self-avoiding-filling-polygon from my graph ...
-1
votes
1answer
82 views

Lp optimal solution question

i have a general question. if there is a general LP problem $c^Tx$ s.t $A\cdot x \le b$, and $x \ge 0$ and assuming that the components of $c$ are non-zero entries then how can I prove that when $x$ ...
0
votes
0answers
25 views

Can matrices be reduced in the same way that Karnaugh maps can be expressed as an equation?

I'm doing linear algebra, and boolean algebra for electronics and I'm wondering if there are any standard mathematical ways in linear to express a matrix more simply without resulting to graphical ...
3
votes
0answers
81 views

Constructing a directed graph from its spectrum

This is related to the following question from cs theory stack exchange: http://cstheory.stackexchange.com/questions/3742/reverse-graph-spectra-problem So it seems as if given a sequence of real ...
0
votes
1answer
20 views

Is there any weighted graph which smallest eigenvalue of its adjacency matrix is greater than 1?

Is there any weighted or unweighted graph which smallest eigenvalue of its adjacency matrix is greater than 1?
0
votes
1answer
50 views

Are perfect graphs always invertible?

Is it always the case that perfect graph is invertible? Also, is it any meaningful relation between inverse of a perfect graph and itself? Thanks.