Path: csiph.com!aioe.org!.POSTED!not-for-mail From: Daniel Bastos Newsgroups: alt.algebra.help,comp.programming Subject: Re: on notation, MM', graph theory, incidence matrix product Date: Sun, 17 Sep 2017 07:51:02 -0300 Organization: Aioe.org NNTP Server Lines: 36 Message-ID: <86mv5t7g4p.fsf@toledo.com> References: <86k20y90su.fsf@toledo.com> <87h8w28xgn.fsf@bsb.me.uk> NNTP-Posting-Host: czbaxA2UCA/sefhlz0UzmQ.user.gioia.aioe.org Mime-Version: 1.0 Content-Type: text/plain X-Complaints-To: abuse@aioe.org User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (windows-nt) Cancel-Lock: sha1:b6BBfEU+Lk+Zh3OgYf3GDxhl02g= X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com alt.algebra.help:4997 comp.programming:8010 Ben Bacarisse writes: > Daniel Bastos writes: > >> Problem. Show that if G is simple, the entries on the diagonals of both >> MM' and A^2 are the degrees of the vertices of G. >> >> I don't understand what is meant by MM'. M is the incidence matrix of >> graph G. By looking at section 1.4, subgraphs, I take that M' must be >> the incidence matrix of some subgraph induced by M, > > No. The notation is confusing but ' is often used for different things > in different places. > >> but M is a matrix, >> so I'm puzzled. AFAIK, I need a set of vertices of a set of edges to >> induce a subgraph. > > You are right. M is a matrix and the ' just means normal matrix > transposition. M is (in general) a rectangular v x e matrix so it can > only be multiplied by an e x v matrix such as the transpose. The > incidence matrix of any subgraph would not be the right size. In effect > you have to deduce the meaning from the only thing that could make > sense. I did happen to consider ' as matrix transposition, but then I (incorrectly) found a counterexample to the claim so I thought I was totally off. The counterexample I found was for a nonsimple graph. >> I appreciate a clarification on the book's notation. Thank you! > > The summary of synbols at the end gives R' as the transpose of R. It's > a shame it was used with that meaning right after some text that used V' > and E' simply as a modifier to mean some subset of V or E. Yes! :-) Thanks very much!