2
votes
1answer
42 views

Algebraic Combinatorics about a Finite Graph

Here is a problem listed on a book 'Algebraic Combinatorics' by Richard P.Stanley. Let $G$ be a finite graph with at least two vertices. Suppose that for some $l \ge 1$, the number of walks of ...
1
vote
0answers
20 views

Compute paths through graph vertex

I have a mesh, in which every vertex has most likely 6 to 8 neighbours. I need to compute like on the picture. For vertex O there are three incoming vertices: A, B and C. And we have these paths: AC, ...
0
votes
0answers
18 views

Irreducible matrices and connected graphs

The adjacency matrix of a simple undirected graph is irreducible if and only if the graph is connected. Here my questions : Is there an efficient method to check whether a matrix is irreducible (I ...
0
votes
1answer
35 views

How to prove the equivalence of 2 affine spaces given that one is the subset of the other one?

For the sake of completeness, I would like to give you some concepts before asking the questions: For every simplex $S=<<x^{0},x^{1},...,x^{k}>>$ in $\Bbb R^{n}$, denote by $H_s$, the ...
2
votes
1answer
32 views

Graph pruning whilst ensuring connectivity

Problem: I have a graph (in this instance, it's represented by a matrix which is $\in \mathbb{R}^{n \times n}$). In the raw graph, all nodes are connected to every other node (except themselves) in ...
1
vote
1answer
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 ...
0
votes
1answer
67 views

Finding the smallest max eigenvalues for related matrices?

While messing around with a spectral approach to a graph coloring question, I happened upon a type of problem I hadn't seen before. Suppose you have two symmetric $n$ x $n$ matrices in the form ...
2
votes
1answer
40 views

Existence of solution for matrix equation $ (I - \alpha A) \bar{x}=\bar{b}$

This is my first question in here and I would be really thankful if someone could help me with understanding the matter. I am solving a matrix equation $(I-\alpha A) \bar{x} = \bar{b}$ for a positive ...
-1
votes
1answer
15 views

Usefulness of Laplacians for directed graphs

Are laplacians for directed graphs used in any algorithms ? For example laplacians for the undirected graphs are used in algorithms such as spectral clustering.
5
votes
3answers
368 views

Recurrence with varying coefficient

Problem 1 $$ {\rm f}\left(n\right) = \frac{1}{n}\, \left[{\rm f}\left(n - 1\right)k_{0} + {\rm f}\left(n-2\right)k_{1}\right]\tag{1} $$ ( This can also be written as ${\rm Q}\left(n\right) = ...
1
vote
1answer
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 ...
0
votes
0answers
22 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
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 ...
0
votes
1answer
27 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
13 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
42 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
119 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
52 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
34 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
48 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
131 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
38 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
25 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
226 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
149 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
35 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
29 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
50 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
60 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
57 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
36 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
61 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
36 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
49 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
154 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
52 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
42 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
51 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
169 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
69 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
81 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
61 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
922 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 ...