20th talk of the series Seminars on Inverse Problems Theory and Applications by Hannes Gernandt from University of Wuppertal, Germany.
Thank you very much for having me and here today I will present a joint work with Jonathan rer from the University of Stockholm and um let’s get started so first I will speak a bit about the original Calon problem so in this problem you have a domain and you have
Minus delation U plus some potential uh on the interior of the domain and you have some derly boundary data on on the boundary of the domain and there you study the D to Norman operator which as the name name says is it’s an operator L2 on the boundary and it sends the dly
Boundary data to here the Norman traces on the boundary and uh what is then calderon’s original problem from the 80s it is regarding the uniqueness so if I have um the de to noyman operator for some domain Omega and for two different potentials q1 Q2 does this then imply
That the potentials coincide and even more there’s a question of reconstructing the potential from D to Norman operator so that’s this is the orig oral Calon problem and where does it appear the original is an electrical impedance tomography where the idea is to recover the conductivity of an inhomogeneous body from current and
Voltage measurements at the boundary which could then be used to to obtain the D Norman operator so let me now slightly or go to a different uh area namely the the colon problem for so-called Quantum graphs so what is a Quantum graph so quite similar
As before we have a domain but now the domain has this kind of graph structure so we have um vertices here the blue and orange dots and we also have edges connecting them you can also think of a boundary which are here the blue vertices or dots uh in this example
These are they have one and we also have here the so-called interior vertices here the orange dots and at these interior vertices uh you might have additional uh interface conditions so you can think of having functions here uh on the edges and on these edges you have a differential
Operator so this is this is what we have here so we have minus second derivative plus a potential so it’s the same operator as before but now on the one one dimensional spatial interval and so here these functions uh on the edges need to satisfy certain interface condition uh typically these are the
Continuity uh C vertex conditions so that means you assume that when you evaluate the functions on each Edge that should be the same value this is the continuity and the sum of the derivatives should be vanish so this is a typical interface condition you consider there and so this this whole
Object like the graph with the differential operators is called a Quantum graph and here we have the same or could formulate the same problem so on the domain we have we have this and on the boundary we have some dly data given and then again we can think of a
De toan Matrix which maps The darly Boundary data to the uh derivative here uh on uh on the boundary vertices yeah and one can even go beyond that one can introduce a spectral parameter here as well so Lambda is a spectral parameter and one can solve then this problem for
Every Lambda and then uh we get uh a matrix valued uh function here and uh this kind of function has some nice properties it’s a so-called Matrix valued hairs never linear pck function which is a well studied object in in oper Theory and uh then again having this
Function we can ask the same question as before in kyon’s problem so here uh results are known for trees in particular if the D to Norman map coincide for a tree and q1 Q2 then it was shown by Yu brown and white card that the potentials coincide furthermore there’s a even
Stronger result I would say that uh if the D le to noral map coincide for two different trees and two different potentials then we can even conclude that the trees coincide and the potential coincide which was shown by afun and kurov so now I will motivate a little
Bit what was our research question of uh the paper I will present you today if we now uh neglect this dependence on a spectral parameter and go for one particular spectral value in particular Lambda equal to zero we can ask the question what can be determin from this
D to Norman Matrix for one particular spectral parameter and in fact there is no hope to recover the potential yeah since we fixed the spectral parameter however we could ask ask could re reconstruct the underlying metric graph which of course has a certain distance function if you think of uh
Measuring distance between vertices and taking to account the length of the intervals and I will directly present you our main result and in the reminder of my talk I we will have a look how to prove that what are the methods so what is the main result for trees we can show
That the set set the potential equal to zero and we can show that if the D Norman matrices coincide then also the trees the underlying trees coincide and even more we have a particular formula so uh if we have a tree with boundary vertices that means the vertices which have degree one then
We have this formula here so here we have some technical expression but here this is just the distance between two boundary vertices so we we have boundary vertex VJ and VI I not and this distance is now determined by the dly to Norman map but it’s not the dly to to Norman
Map it’s some uh modification of it it’s a matrix which can obtained from the DD to Norman map by setting the I not diagonal entry to one and all other entries to zero then you take the inverse of this Matrix and here this is just the Scala
Product this is the canonic unit Vector so you could say this is just a fancy way of writing uh the diagonal entry of uh this inverse Matrix so the distances between boundary vertices can be determined from D to Norman Maps directly and uh we will then see later I
I will explain you a bit the details that knowing the Parise distances between bound vertices of tree already determined is tree unique so this is this is one key idea and so this is the main result and now I will show you uh how uh we Pro this and
Actually uh I will leave now the quantum graph setting and go to a discrete setting because the result we showed is is in fact for for discrete graphs or discrete graph locations as they also called so let me briefly recall what discrete graph loation is so you consider
Squared matrices you have a graph and on the edges you have a certain weight w and then the graph liation is defined like that on the diagonal you just sum all of the weights of all adjacent edges to a certain vertex VI and on the non diagonal entries you uh just set minus
We the weight um if you have that connects vertex VI with uh vertex VJ and you can also rewrite that like how uh would it act on a vector and then you have somewh here these let’s say call it weighted differences here which are summed up you see if you reorder the
Terms you you get this sum here again so this is uh this is the discrete graph liation I think most of you know this and it has also some nice uh structureal properties it is easy to see that it is a symmetric Matrix and also uh one can
Show uh for example using gorin theorem that it is a positive semi-definite Matrix and um also quite interesting is uh that uh the kernel that so kernel of this Matrix somehow describes the connectivity of the graph in a certain sense for example it’s known that the
Kernel uh so zero is always an I value of the graph loation so just take the all one vector for instance and um you see that the dimension um of the Kern is one if and only if the graph is connected that means you have uh a path
Between any two vertices in a graph so towards dly to map for discrete graphs let us consider uh the normal derivatives at the boundary vertices which are defined in the following way so if VI is a boundary vertex just consider here the sum and somehow it resembles here the difference yeah so
You can really think of this like some discrete uh derivative and um some more notation so towards um having functions um which on the discrete graph which are prescribed by their boundary values we consider here this potential it’s not a potential this function f which is defined on the boundary
Vertices and then there exists a unique function on the whole graph or the whole set of vertices um which is zero at all interior vertic or not the function liation applied to the function zero for all interior vertices and if you evaluate this on the boundary vertices
It is precisely the function pi and this is some some notion from the literature uh it is called harmonic extension of this boundary uh value F and with this we can Define the D toon map or in fact Matrix of a discrete weighted graph so uh if you consider the
Boundary vertices we1 to we k then the D toon Matrix is defined by this relation so here for the function five we take the evaluation at the boundary vertices and we map that to uh the normal derivatives so we take derly boundary data to to noron data and uh of
Course it’s not hard to see that this is a is a linear map and um and yeah and here this U Pi is exp that’s that’s harmonic extension so in in such a way you can Define the dly Norman map or for discrete graphs as well so what one can
Also easily check I will not do it here is that the Matrix is symmetric that’s again simple but you can also show that it is positive semi-definite or here the terminology from operator Theory non- negative yeah means the same um and um yeah uh of course you can also think of
Some special cases so uh if uh for example you have only two vertices with one connecting Edge then uh it coincides with the lation in fact the graph liation and if there are more boundary vertices then uh something quite interesting hold so what you can always
Do by resorting the vertices to write to split the graph loation in such away yeah and here we just as I have done it before I consider the vertex V1 to VK to be the boundary vertices and here we have then uh just the uh the the weights
Uh of the edges uh or um at the boundary now the boundary um edges and um and then we have the remaining Raff PL so to say so here these entries this part corresponds into all other vertices which are not boundary vertices so you can always
Write the graph Li such way now there’s a nice connection which was already already observed by Curtis Ingman and morrow in 98 so um in fact this L head Matrix here is invertible and the dly to Norman Matrix as I have defined it previously is equal to the sh complement yeah which is
Here taken uh uh in this sense yeah so um so graph D nor equals D head minus here this B transpose L head inverse B so there’s a a nice connection between a dly to Norman Matrix and uh the graph loation or to some extent inverse inverses of um yeah parts or
Restrictions of the graph loation so that’s very important result and remember that I want to recover this tree structure and to do this uh we will now uh restrict the graph to be a tree because somehow you see that uh to to determine a d to Norman Matrix I need to
Work with with inverses of flti and that’s hard for Generate graph so now uh we restrict to trees for this Rec uh covering procedure defining the D to can of course be done for arbitrary graphs so but now I I would go for trees and um for the tree
Uh it I can define a natural boundary as you have seen it before in this qu graph picture for instance uh I take all the vertices that have degree one and say this is my boundary so now um to recover now uh the distances between boundary vert we use
Some uh yeah nice lar from paperback Kirkland Shader and to uh to apply this yeah to to recover the distance I need to introduce the so-call reduced LA and for this I take the graph LA and I fix a Vertex V and what I do then is I remove
A line and column which corresponds to this vertex V and then I get Matrix which is again squared and of one uh Dimension smaller yeah uh and then uh we have the following result I Kirkland Shader so uh it says that now that the inverse of this
Reduced loation is related or can tell me the distances between uh two vertices so in particular if I uh consider uh here such a set P J so it’s a set of edges that are on both the path from V VI to V and the path from v j to V yeah
And uh V is the fixed vertex uh which which somehow determines the reduced liation and now the entry IJ of this Matrix equals here uh the sum of the inverse weights yeah and I sum over all of the edges which are from the set PJ so and this this really tells me that
That the entries are related uh to the distance uh between uh two vertices so um I spoke about equality of graphs so let me be a little bit more precise now uh what we mean by that so if we have two weighted graphs then uh we can say that they’re equal or we
Define them to be equal if they have the same number of vertices and there exists a permutation Matrix such that uh the the graph loation coincide you can just say you you relabel the vertices then the graphs are are equal and for some reason this notion is too strong so uh
If you want to recover graphs uh because the problem basically is that we cannot distinguish between an edge and uh an edge uh where a vertex of degree 2 uh is located yeah and um this this is why we uh use a different notion we say that
Two weighted graphs are equal up to vertices of degree two yeah as the name says if uh yeah they are are equal after removing this interior vertex of degree 2 and there’s also a way of how to replace the weights so if you have this interior vertex uh you have then uh two
Weights yeah because you have two edges then you need to when you remove the edge you need to adjust the weight in in a certain sense and this is done by combining the inverses of the weights and this also has some some interpretation in terms of resistance uh
As I will show you in the following so why why is it done in such a way yeah um so how can we now Define a distance uh in a weighted tree yeah as I said uh we recover the distance this is the main idea and from recovering distances we
Can Rec recover the tree structure okay so um since G is a tree we have a unique path which connects to vertices and then we Define the distance in the following way yeah this is somehow uh the uh counterintuitive because we have a certain weight which
Is we on the on the edges but the distance is not the sum of the weights but it’s the sum of the inverse weights yeah this is the distance we will consider and which we can determine from the D to Norman map and um the reason somehow that for these conductivity
Problems which are also con consed for graphs uh is that the weight is the the conductivity and the inverse of the rate is the resistance and in in that sense uh this distance we consider there is a well studied object there’s this nice paper on a resistance distance this in
In graphs um from from 93 and in that sense yeah this is somehow the right distance for for discrete uh graphs now uh let me come to a LMA I’ve mentioned it a few times uh already uh it’s somehow a well-known result we think so we did not include the proof in
In the paper actually we found this in a PhD thesis by rukan who did his PhD also on on Spectra of quantum graphs and but again the result has nothing to do with with Quantum graphs but just with graphs so if we consider two weighted Rees with certain boundary vertices they have the
Same number of boundary vertices yeah this is assumed and we also assume that the pairwise distances between any two boundary vertices of the graphs coincide then uh one can show that G1 and G2 two graphs coincide up to vertices of degree 2 let me briefly sketch to prove so the
Idea is that you just pick two boundary vertices and we assume that there is an edge of length um uh the uh distance between uh the two um vertices yeah and um somehow this in in the process this Edge might be replaced by some path between the boundary ver ver course
Actually there’s there’s no Edge but we think of it uh like that for the moment so now what happens if we so we proceed inductively in in the proof so um if we consider a third boundary verus you can have a look at the sketch here the main
Idea is that you know by assumption all the pawse distances here so you know the distance from V1 to V3 V1 V2 V2 V V3 and uh the the IDE is that if you know all these distances and assume that there is some some point here some some
Additional vertex W um then you can just calculate the distance um and and you can determine a unique point w just from the distances and so you will get some star graph here and uh this procedure can be repeated so if there are even more boundary vertices uh you can you
Can repeat that and you will obtain a unique uh graph by by doing this and this this shows then that the the tree is uniquely determined from Norse distances uh of each uh pair of boundary vertices okay that was that idea now I will formulate the main result for
Discrete graphs so if we have a tree with a boundary again yeah and we have the D Toyman map and uh then we have again this this strange Matrix which results from the dly to Norman map by applying uh the following operation so uh we replace this diagonal entry with index I
Not by one and all other entries in the corresponding row and column by zero this is a matrix which recall I stick here to the notation used in the paper it’s called SI not and um then we have this formula you might recognize from the from the beginning of my talk one
Can show that s i not is an invertible Matrix and here again this is a way of writing uh the J diagonal entry of this Matrix this gives you directly the uh the distance uh between the two boundary vertices VJ and VI nor so by just having this dly to Norman uh
Map we can uh compute all of these matrices as I not for all I not running through the through the boundary vertices then we compute the inverses and then we uh uh then consider all of the boundary values then we let J run through the through the uh from from I
To K yeah and by doing that um we get uh then all pairwise distances between boundary vertices and this now shows yeah with the with the previous Lama by by ran that uh the tree is uniquely determined from that yeah so in particular we can recover the tree structure from knowing
The dearly to Nora Matrix the proof actually is not um um yeah it’s rather simple I would say it’s maybe one page of proof uh but it involves some technical calculations which I will not show you but I already presented you the main ideas um so let me now come back to the
Quantum graph case so if we have now uh I will now in certain sense build a bridge now back to Quantum graphs how to how to get the result for Quantum Gra graphs I showed you in the beginning now and uh if we have a graph with weight
We then uh we consider the corresponding metric graph where we now view the edes as intervals and the length is then one over we the the the weights and uh we can also consider then functions on this this metric graph uh in a natural way and typically
We are interested then in in considering function from H1 so two times weekly differentiable with derivatives in A2 that’s a typical space because we want to uh consider minus second derivative there um and we can also Define the normal derivative then so since uh we have here
That on the edges the function are on H2 we can consider here the derivatives um they are they’re continuous and we can evaluate them then on the vertices and here it’s important how to define the derivatives but here the derivatives are taken in the direction towards the
Vertex so by using this notation now we have a function defined on Gamma or metric graph so we can evaluate the function on the boundary vertices and we have also here the the derivatives uh evaluated uh at the boundary vertices and we can uh by by doing that we can also Define dly
To noral Matrix now and um yeah by by by considering again think of this construction using the harmonic extension uh you can consider here functions uh where the second derivative vanishes uh on each Edge and which will fill these standard kof condition that means that this the sum of the
Derivatives is zero at the internal vert and that I have continuity at in vertices there also it can be shown that um defining the dly to normal Matrix like that is uh uh yeah works out quite well and this is this done in this uh this book here it’s uh it’s the
Introduction to Quantum graphs uh from 2013 that’s quite good reference for for Quantum graphs so uh finally now from uh from the mg so the the the nor from discrete graph to the one for the quantum graph so uh if we consider our function which is harmonic on every Edge so second
Derivative vanishes and satisfies this continuity Cur of conditions at the uh interior vertices then we can uh somehow um um I mean it is clear that since the second derivative end is that f is a linear function each Edge and uh then um uh we we can uh write it
Write it like that now um it’s a linear function and um one can then compute the derivative and by doing that uh we can we see that so if you consider uh these use which arise from the Restriction uh of this um this function f on the metric graph then I I recover
This formula so app plation applied to this is then just some of the derivatives uh here and and and it’s also zero on the interior vertic this is this was just a definition uh of the Der to noron map for discret craft so in fact by using uh
This construction here we see that uh both directly to noron Maps or matrices coincide and uh in this sense we have now seen by using now our main result on discrete graphs that uh also uh knowing the direct Norman map of a Quantum graph determines the tree
Uniquely okay let’s have a look at two examples first example is I mean both examples are in show in a certain sense that the results are are sharp in a certain sense in the first example uh the main message is that Cycles cannot be detected from the dly to Norman map
That means if we consider two graphs here G1 where one this this one contains a cycle and the other one’s just a star graph and you choose the weights or the length of the edges uh in a certain way namely here I choose one for all and here in G2 I
Choose it slightly larger and uh one can show that uh the the dly to noral Maps coincide for these two graphs yeah and um just um we can just do the calculations if you like so first of all you would consider here the graph loation the discrete one um by our
Labeling if you remember the first entries are the boundary vertices so we have here 11 one one as a degree and we have three interior vertices which are these three vertices and they all have degree gree and since the weight is one you sum all the weights and the other
Entries are then so you get three here on the diagonal and the other entries are here the minus one so this is this isation discrete graph loation and um as I showed you there is this result on the uh how to obtain a dly to noron map
Directly just by using the sh complement and if you calculate this it’s not hard to calculate here this inverse Matrix you will end up with such a matrix yeah so um okay so this is the first graph let us look at the second graph can do the
Same it’s a star graph so again you have three boundary vertices so on the graph loation we have this one yeah this is the weight and since there’s only one Edge you have directly this weight here and there’s this one Center vertex the interior vertex uh which is connected to
All boundary vertices so this is again a graph loation again you can apply a shoe complement here inverting uh this entry is is much easier yeah and so um you might not remember the The Matrix on the last slide but it’s easy to check that in fact this is this Matrix again so
Both coincide and by that we see that the D to normal Matrix alone does not determine the graph uniquely if we have Cycles so we cannot uh yeah get more information from this dly to Matrix for this one particular spectral value yeah furthermore um if I have only partial
Boundary data value available then this does also not determine uh the the tree structure which is also not surprising uh I would say so in particular we consider here two graphs so you can think of this as uh having the graph G1 so again a three star and then just you remove one
Boundary vertex so then you have only one Edge left which is the graph G2 again you choose the The Edge length or weights in a suitable way and uh you can you can see then that um if you restrict uh only to uh a certain number of
Entries in a directly to Norman map then you you cannot tell if it’s the larger graph or if it’s this graph so uh but I will show you the calculations so uh the graph loation we have seen this in the previous example that’s that’s quite clear and for this one it’s it’s only
You only have one Edge yeah two vertices and this is given by that yeah so it uh it remains to uh to compute the Restriction of this dly to noral map so this is done now on this slide so uh if I consider now uh the the uh dly
To Norman Matrix uh only with respect to two boundary vertices then I get this formula so here again the diagonal entry is then inverse and of the remaining two vertices and I arriv precisely at the same uh dly to Norman map uh as for the graph which
Consists only of of one Edge yeah so was mg2 this shows that uh as I said partial knowledge of the derly to nman Matrix does not uniquely determine the tree and I’m already at the end of my talk so here is a list of references uh uh on the subject so uh I
Just sorted them alphabetically there there is a lot of work which was done already in the ’90s by Curtis uh and moral uh who also study dly to Norman Maps um there’s also quite interesting in a Quantum graph case there’s this recent book by by pav kurasov on spectral geometry of graph
Who also studies uh this this inverse problem um I showed you for for Quantum graphs and it’s also nice that it is open access uh and furthermore there’s this reference byman if you more interested in the colon problem he summarizes 30 years of the colon problem so very valuable reference and um also
There has been really recent work here how to recover conductances on not tree GRS but so-called spider networks yeah so there there’s a lot of uh research going on there and uh with that I would like to thank you for listening and I’m open for questions