0
votes
1answer
66 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
22 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 ...
0
votes
0answers
109 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
129 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
1answer
23 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
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
0answers
36 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
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
52 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
15 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
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 ...
0
votes
1answer
42 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
26 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
39 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
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 ...
1
vote
2answers
35 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
35 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
35 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
31 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 ...
0
votes
0answers
38 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
121 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
59 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
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
47 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
906 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
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
52 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
69 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
257 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
53 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
79 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
23 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
71 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
19 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
48 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.
0
votes
1answer
28 views

I have a recursively defined function, and another function involving powers of a matrix. How can I show that they are equal?

The problem is Let $A$ be the $n \times n$ adjacency matrix of a graph $G=(V,E)$ on $n$ vertices, i.e. $A=(a_{ij})$ and $$a_{ij}=\begin{cases} 1 & ij\in E \\ 0 & ij\notin E ...
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
126 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 ...
1
vote
1answer
93 views

Spectrum of the adjacency matrix of strongly regular graphs

I am working through a proof of the following Theorem: Let $G$ be a connected, $k$-regular graph, $G\neq K_n$, then $G$ is strongly regular if and only if $|Spec(G)|=3$. Now I am having trouble with ...
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
1answer
57 views

Can a directed hamiltonian path be found in polynomial time?

I was discussing a programming competition problem with one of my math professors in Linear Algebra that reads as follows: A matrix is an $r\times c$ array of numbers, where $r$ is the number of ...
7
votes
1answer
102 views

When does this matrix have an integral square root?

Let $d_1$, $d_2$, ..., $d_n$ be positive integers. Let $B$ be the $n \times n$ matrix $$\begin{pmatrix} d_1 & 1 & 1 & \cdots & 1 \\ 1 & d_2 & 1 & \cdots & 1 \\ 1 & ...
2
votes
1answer
52 views

How would I prove that the determinant reduced Laplacian of a graph is independent of the choice of $i$?

My homework problem gives us the definition of the Laplacian matrix $L(G)$ of the graph (the degree matrix minus the adjacency matrix) and the reduced Laplacian $L^i(G)$ (remove the $i^{th}$ row and ...
0
votes
1answer
58 views

Approaching of area and perimeter of a regular polygon to that of a circle

When regular polygon approaches to circle its area and perimeter also approaches to that of a circle. Can you graphically show that ?
0
votes
0answers
30 views

Graph Theory and sandpiles

Using Matrix-tree theorem how could we conclude the order of S(G) is the sum of the weights of G's directed spanning trees into s where S(G) is the sandpile group of a sandpile graph G=(E,V,s).
0
votes
1answer
39 views

Diffusion on a weighted graph

I have a weighted graph and want to apply a diffusion step to it. I read this paper, where they formulate such a diffusion step for unweighted graphs: $Z_i(t+1)=Z_i(t)+\alpha\sum_j ...
3
votes
0answers
112 views

What can we say about two graphs if they have similar adjacency matrices?

Suppose we have two (finite, simple, undirected) graphs, what can we say about these graphs if they have similar adjacency matrices? Observations to begin with: If $G_1$ and $G_2$ are isomorphic, ...