Posts about math (old posts, page 1)

Academia, part 1. Research supervisors -- necessity.

Academia is conservative. It's got a central tendency which results in a highly-coupled federated system with a rather high entrance barrier. One of the requirements has so far been that you must follow a scientific supervisor... until it's time to lead. The new communication capabilities make us question the position of this and many other established attributes of Academia. We ask why it's so and conclude that the scientific community needs to learn a decentralized way from software developers

The questions

Sat, Feb 16 2018, visiting AG Baskakov I finally get to try and discuss these problems as well as the perspectives of research in and outside Voronezh.

Here I will just outline some propositions of AG Baskakov addressed to a student standing just in the begining of his path. I believe these propositions pretty much describe the way Academia is today. The quoted are the translated pieces of our dialogue and the rest are my comments.

  • "You won't achieve anything without a supervisor", i.e. you must begin with a supervisor.
    • "Try and find any recognized mathematician who made it his own way. You won't find one! There was Gallois but he grew up in France", i.e. an appeal to history.
  • "You also don't need anyone besides a supervisor", it suffices to have a supervisor.
  • "You don't need people of your generation" --- you could think you need a competitive environment, someone to share and exchange ideas with, an inspiration for something completely new, or solving some applied problems in "background", but you really don't. These things are optional.
  • It doesn't matter if there aren't in the city many other people doing real research or if the most researchers at the university aren't exactly in tune with the rest of the world. Apparently, you're supposed to abide.

How it came to this

Newton said:

"If I have seen further it is by standing on the shoulders of Giants"

It is known that Science isn't built just by a man --- man's life's too short. Science isn't even built by men of a generation --- we only further the knowledge acquired by the predecessors as far our abilities allow and our needs require us to. Hence 'tis natural that humankind's knowledge was commonly being developed by groups of people following the most prominent of us, then by the ones who followed the followers, and so till us. It's an ever evolving system with many branches and clusters. But its key feature to note is that one's first struggle always is finding an entrance. An entrance is someone who'd become their advisor, their teacher, and mentor. Someone whose line they would follow and further.

Is there no fallacy? Do ones have to find themselves what's basically a second father? Do they have to choose a single line and can't one pursue many?

It just wasn't feasible before but it may be now with the new technology. The many pieces that are the Scientific Knowledge today we could build together into a connected system available to everyone. The current state of research, the latest challenges and achievements could be tracked online in a consistent way. We could provide a guidance for newcomers in the form of manuals&tutorials, as well as lists of open issues, ranked and classified. That's what engineers and software developers are used to do. That could be the entrance. That could smoothen this steep learning curve and lower the threshold.

Yet not only could it be an entrance it could also define the workflow. We already have open review systems. We've even got services resembling social networks for scientists where you could track one's path and interact in some ways. We've got git for cooperation. We saw outstanding systems evolve with many independent contributions of many unrelated people in an almost random manner1. We know now that this randomness also provides some validation of the result and increases the robustness. Academia oughts to adopt and improve these decentralized methods.

Conclusion

An appeal to history doesn't seem to be a convicing argument. I believe supervisors as they are now at least can be optional though it'll always be easier to be guided by someone experienced. The immediate concern should be making research contribution-friendly and adopting the existing task-tracking and version control tools for common research. We shall keep the image of FOSS community in mind. It's only an initial stage and we shall learn our needs in progress before we can build more elaborate tools.

See the next writing in this series.


  1. Raymond, Eric. "The cathedral and the bazaar." Knowledge, Technology & Policy 12.3 (1999): 23-49. URL: www.catb.org/esr/writings/cathedral-bazaar/ 

Academia, part 2. Research supervisors -- sufficiency.

We've talked a little about certain aspects of Academia in the previous writing. Specifically we've tried to cover the question of whether it's necessary to find and follow a supervisor. Now we're questioning the sufficiency part. The main argument for insufficiency is the problem of an emotional burnout.

Just like writing or software development, research is a kind of activity that may lead to a burnout. There are different ways to deal with it. For example, one person said1 that

"There are two math schools in Voronezh. There's the school of the followers of Kipriyanov --- these are the ones who drink, and there's a school of Baskakov --- the ones who run"

But if we mean to take the problem seriously, as we do, we must admit that drinking isn't a reliable solution and running's not enough.

To be continued


  1. TODO: Attribution? 

Data models

Every now and then I hear people talking about "modeling data" and usually it doesn't make any sense. Whereas there are some activities that can be called so, I'd bet when You say either of "modeling data", "data modeling", or "data model" you actually mean modeling real-world processes as or with the use of data. The distinction could be the key to the question: what's so much wrong with modern software?

First attempt

Here I propose two definitions. They're both debatable.

Data is a model of a part of the real world. The model of data then should probably refer to the methods of manipulating and persisting data. It's a low-level implementation detail detail.

These propositions immediately lie down two things: 1. We're solving the problem of modeling the real world and probably we want to model it with data; in other words, we're interested in "modeling using data". 2. The mainstream tools (SQL and OO when used to describe data) are rather focusing on the problem of "modeling the data", which isn't what we're essentially interested in.

Object model

My story with OOP begins in childhood when I was struggling with my despair in school. Long story short, I got my hands dirty with dotnet, and I liked it at the moment. By the end of school years I'd tried lots of things: from network programming with sockets to games with XNA to UI with WPF to webdev with aspnet mvc. I was messing around mostly, and it was all rather childish. But the thing is I got quite familiar with the environment and concepts. I loved it. MSDN was my holybook. Most importantly, I considered myself an adept of OOP. Now I reproach all of that and here's why.

I will try and not rant on Microsoft and the proprietary software. Instead I'll focus on OOP.

I can see two basic approaches to the Object Model or rather two different Object Models: - Structure on sets. - Interacting entities.

Structure

The first approach is the Light Side of the Force. It is built around the idea of endowing Sets with Structure, i.e. relations and functions. If a mathematician would reffer to a set together with a structure on it as to a Space, an OOP adept would call it a Class or a type of Object. Object here is simply an element of a space. The process of grouping sets and structure is known as incapsulation.

Interacting entities

The second way is a way of the Dark Side. It's a model of interacting entities. Here objects are mysterious entities that act with their functions on their states. They can share behaviour with the use of inheritance. I'm not mentioning the principles like polymorphism here as they aren't really specific to nor distinguishing for this model.

I don't imply that local interactions is a bad idea: actually it's a great idea, but you must take care of... convergence of some sort. I say it's a dark path because it's easily followed uncounsciously. And when it's followed so it leads to misinterpretations, to the cargo cult, and, above all, to errors.

Inheritance is useless

Inheritance is a means to implement polymorphic behaviour, no more. In this context almost always the Inheritance is overused and only makes a system more complex: it either can be replaced with composition or even stripped away. The main problem though is that it's tempting to use inheritance to describe hierarchies, although there's no practical reason to. A classic example is that of a square and a rectangle: the first is a particular case of the latter but the setWidth() of a Square should either violate what we expect from a Rectangle or return a non-square.

Another use of inheritance is for Mixins. While it's an acceptable use it's still an overuse. My belief is that one can replace it all with plain datastructures.

OOP as an instance of cargo cult

Or a way to avoid solving the problem.

The main grudge of mine against the OOP is that it introduces a lot of unmotivated concepts which have been taken for granted by the mainstream and are being applied to every single problem. People started modeling data with interacting objects! How do you start building a web service in some java or, say, django? You describe models (which aren't actually models) using classes which inherit from ORM-framework's base types (from django.db.models or javax.persistence). These quasi-models then need to be mapped into the relational ones. This mapping causes some additional conceptual difficulties and also poorly affect the performance. Some time later you'll have to fix the performance. How are you going to achieve that? You'll write custom queries which will take into account the relational nature of data. Moreover, sooner or later you'll find out that a typical RDBMS's model is rather stripped and incomplete because of some dogmata and myths associated with the relational model (I'll write on that later). One can find much more points to this topic by googling "object-relational impedance mismatch" or something.

Shall we dig a bit deeper we'll realize that not only there's a mismatch between applications' data model and persistence-layer's model, but also a mismatch betwixt application and the presentation layer. For what it is that frontend expects from the application? A REST api for WEB or plain datastructures for a standalone application that relies on data-bindings. Not a "bunch of interacting entities" at all

The only part left is the domain logic the vast part of which consists of all kinds of constraints. Ideally we'd like to write just a specification of these constraints and then use it for both validation and input-suggestions.

To sum up: the object model isn't how we store data, nor how we serve data to the end-user nor even how we'd like to modify and validate data.

Basically the coders are writing lots of code which doesn't produce any additional value. That happens because it is convenient to follow the routine: write resource classes, write the services, generate the sql and the REST endpoints, write some tests, proceed as usual. This process doesn't really involve thinking. Convenient indeed. The only caveat: people produce erroneous unmaintanable shite which somehow keeps working as long as an employer keeps paying the employee. It may seem feasible given that modern society is all built on deprecated, unsustainable, and self-destructive methods. It may so far but there's a line. We haven't reached it yet and we can't see it, but that doesn't mean it isn't here.

When object model makes sense

Of course "interacting entities" can be useful too. For example they are sure useful when it comes to modeling a system that consists of... stateful interacting components! Usually that happens at at lower layers; at he level of architecture. E.g. in the components that manage the lifecycle of an application. Yet even there the functional approach is coming.

Relational model (INPROGRESS)

It isn't justified to call a relational model what people usually mean when the talk about a relational model. The common normal form constraints are treated in a dogmatic manner which leads to several troubles including, but not limited to: inconsistency with set-theoretic notion of a relation, extremely verbose DDL, broken integrity guarantees, impedance mistmatch, and poor software performance. Apparently the solution is to implement higher-order logic.

Optimal control, criteria (INPROGRESS)

Cheatsheet for Zadorozhnii' optimal control course. So the credit for whatever's correct goes to Zadorozhnii and all the errors are to be considered mine. Some refernces (specific to the course mentioned):

  1. J. Warga: https://libgen.pw/item/detail/id/1199754?id=1199754

Consider a general problem \[ J(x, u, t_0, t_1) = \int_{t_0}^{t_1} f_0(t, x(t), u(t) \mathrm{d}t + \Phi_0(t_0, t_1, x(t_0), x(t_1)) \longrightarrow \inf, \] subject to \[ \dot x(t) = f(t, x(t), u(t)), \] \[ \Phi(t_0, t_1, x(t_0), x(t_1)) = 0. \] \[ u\in\mathrm{PC}(\mathbb{R}, \mathbb{R}^n). \]

Lagrangian

As usual we use the Lagrange's multiplier method in order to reduce the bounded problem to an unbounded one: \[ L(u, \lambda_0, \lambda, \mu) = \lambda_0 J(x, u) + \int_{t_0}^{t_1} \langle \lambda(t), \left[ f(t, x(t), u(t)) - \dot x(t)\right] \rangle \mathrm{d}t + \langle \mu, \Phi(t_0, t_1, x(t_0), x(t_1)).\]

Hamiltonian

Let us introduce the helper functions with the formulas \[ H(t, x(t), u(t), \lambda_0, \lambda(t), \mu) = \lambda_0 f_0(t, x(t), u(t)) + \langle \lambda(t), f(t) \rangle, \] \[ l(t_0, t_1, x(t_0), x(t_1), \mu) = \langle \mu, \Phi(t_0, t_1, x(t_0), x(t_1)) \rangle. \] Now we can rewrite the Lagrangian: \[ L(\cdots) = \int_{t_0}^{t_1} \left[ H(\cdots) + \langle \dot \lambda(t), x(t) \rangle \right] \mathrm{d}t + l(\cdots) + \langle \lambda(t_0), x(t_0) \rangle - \langle \lambda(t_1), x(t_1) \rangle. \] Here \[ \langle \lambda(t_0), x(t_0) \rangle - \langle \lambda(t_1), x(t_1) \rangle = \int_{t_0}^{t_1} \langle \lambda(t), -\dot x(t)\rangle \mathrm{d}t. \]

Variational calculus, criteria (INPROGRESS)

Consider a general problem \[ J(x) = \int_{t_0}^{t_1} f_0(t, x(t), \dot x(t) \mathrm{d}t + \Phi_0(t_0, t_1, x(t_0), x(t_1)) \longrightarrow \inf, \] subject to \[ \Phi(t_0, t_1, x(t_0), x(t_1)) = 0, \] \[ x\in \mathrm{PC}^{(1)}(\mathbb{R}, \mathbb{R}^n). \] Automagically reduces to optimal control problem.

Euler's equation

Legendre's criterion

\[ \frac{\partial^2}{\partial u^2} H(t, \cdots)\left.\right\vert_{x_\star, u_\star} \geq 0 \] or equivalently: \[ \lambda_0 \frac{\partial^2}{\partial {\dot x}^2} f_0(t, \cdots) \geq 0\ \text{at} \ x_\star, \dot x_\star. \]

Weierstrass's criterion

\[ \mathcal{I}(u) \geq \mathcal{I}(v) + \langle \mathcal{I}^\prime(v), u \rangle \]

Jacobi's criterion

Zadorozhniy and Monty hall problem

Zadorozhnii and Monty Hall problem

We consider slightly different statement proposed by Zadorozhnii: say there's a hostile aircraft at $L$ --- one of the locations $\{1,2,3\}$ and you're a fighter pilot that is asked to destroy the aircraft. You pick some location $X\in\{1,2,3\}$. Now suppose you get an intel from the HQ that informs you that the location $C\neq X$ is clear (i.e. $C\neq L$).

Shall you switch your target?


First on Monty Hall: there are three doors with a car behind one of them and goats behind the rest. You pick one door; the host of the show (who knows where the car is) opens another door and (always) reveals a goat. Despite the first thought may be that both closed doors are now equally likely to contain the car the fact is that switching is better. Here's why: when making an initial choice you end up picking a goat-door in two out of three cases. Then there's only one goat-door left for a host to choose from and the only unmentioned door is the one with the car. The only case when switching leaves you with a goat is when your initial choice was a hit which happens rarely: it is only one out of the three cases.

More rigorously. The probability space is $$\Omega=\{ (L,X,R);\ L,X,R{=}\overline{1,3} \}$$ with $L$ the true location, $X$ the initial choice and $R$ the host-revealed door. The natural assumption is that $L$ and $X$ are uniform, i.e. the marginals are: $$P(L=l)=\frac13,$$ $$P(X=x)=\frac13.$$ The skewedness of the Monty Hall problem comes from the conditional distribution of $R$. If you happen to pick the right door ($X=L$) then the host might open any of the two doors left at random: $$Pr(R=r\ |\ X=L,\ R\neq X) = \frac12.$$ But whenever you draw a goat, the host is bound to reveal the only losing position left: $$Pr(R=r\ |\ X=x,\ L=l,\ x\neq l) = \left\{\begin{aligned} & 1, && r\notin \{x, l\},\\ & 0, && r\in \{x, l\}. \end{aligned}\right.$$

Suppose we initially pick the door $x=1$ and the host opens the door $3$. $$Pr(X\neq L\ |\ X=1,\ R=3,\ R\neq L) = \frac{ Pr\left\{ (2,1,3) \right\} }{ Pr\left\{ (1,1,3), (2,1,3), \right\} } = \frac{ \frac19 }{ \frac12\frac19 + \frac19 } = \frac23$$

In [1]:
import numpy as np, pandas as pd


N_ITERS = int(1e6)
np.random.seed(431)


class IntelProblem:

    def __init__(self):
        self.cnt = dict()
        
    def test(self, exclude=['X', 'L']):
        X, L = np.random.choice([1, 2, 3], size=2)
        remaining = [1, 2, 3]
        for v in exclude:
            try:
                remaining.remove(locals()[v])
            except:
                pass
        R = np.random.choice(remaining)
        self.cnt[(X, L, R)] = self.cnt.get((X, L, R), 0) + 1
        
    def distribution(self):
        n = sum(self.cnt.values())
        return { lxr: cnt/n for lxr, cnt in self.cnt.items() }
        
    def distribution_df(self):
        df = pd.DataFrame(columns=['LXR', 'p'],
                          data=[i for i in self.distribution().items()])
        df[['L', 'X', 'R']] = df['LXR'].apply(pd.Series)
        df.drop(['LXR'], axis=1, inplace=True)
        return df.sort_values(by=['p', 'L', 'X', 'R'], ascending=False)
In [2]:
mh = IntelProblem()
for i in range(N_ITERS):
    mh.test()
mh.distribution_df()
Out[2]:
p L X R
9 0.111499 1 3 2
6 0.111268 3 1 2
10 0.111211 2 1 3
3 0.111209 1 2 3
0 0.110904 2 3 1
4 0.110473 3 2 1
2 0.055789 2 2 3
11 0.055741 3 3 1
5 0.055690 1 1 2
8 0.055534 2 2 1
7 0.055400 1 1 3
1 0.055282 3 3 2
In [3]:
def switch_stick_probs(model):
    p_switch_wins, p_stick_wins = 0, 0
    for (L, X, R), p in model.distribution().items():
        if L == R:
            continue
        if L == X:
            p_stick_wins += p
        else:
            p_switch_wins += p
    return p_switch_wins, p_stick_wins
In [4]:
SWITCH_STICK_MSG = 'In general: switching wins with prob. %s and sticking wins with prob. %s'
p_switch_wins, p_stick_wins = switch_stick_probs(mh)
print(SWITCH_STICK_MSG % (p_switch_wins, p_stick_wins))
mh_dist = mh.distribution()
print('Pr(switch | chosen 1, revealed 3) = ', mh_dist[(2,1,3)]/(mh_dist[(2,1,3)] + mh_dist[(1,1,3)]))
In general: switching wins with prob. 0.6665639999999999 and sticking wins with prob. 0.333436
Pr(switch | chosen 1, revealed 3) =  0.6674889413063964

Now let us consider the jet fighter's problem. Suppose that the aircraft is located at $L\in\{1,2,3\}$ (equiprobably). Then we make at random the initial choice $X$.

The question is: how the headquarters behave?

Suppose that once we report our initial choice HQ decides to pick and scout one of the locations left: $R\neq X$. After that the search team might have either discovered the aircraft (then of course you'll switch to the right target) or found out the sector's clear.

In this model, if you pick $X=1$ initially and then you get informed that $R=3$ and this location is clear ($R\neq L$), the posterior probability of you picking the wrong target is:

$$Pr(X\neq L\ |\ X=1,\ R=3,\ L\neq R) = \frac{ Pr\left\{ (2,1,3) \right\} }{ Pr\left\{ (1,1,3), (2,1,3) \right\} } = \frac{ \frac12\frac19 }{ \frac12\frac19 + \frac12\frac19 } = \frac12$$
In [5]:
fhq = IntelProblem()
for i in range(N_ITERS):
    fhq.test(exclude=['X'])
display(fhq.distribution_df())
print(SWITCH_STICK_MSG % switch_stick_probs(fhq))
fhq_dist = fhq.distribution()
print('P(switch | chosen 1, revealed 3) = ', fhq_dist[(2,1,3)]/(fhq_dist[(2,1,3)] + fhq_dist[(1,1,3)]))
p L X R
15 0.055859 3 2 2
12 0.055798 3 2 1
9 0.055760 2 2 3
10 0.055678 1 2 3
0 0.055676 3 3 1
5 0.055631 1 3 2
7 0.055618 2 3 1
16 0.055607 2 2 1
6 0.055603 1 1 2
4 0.055572 3 1 2
13 0.055563 2 1 1
14 0.055547 3 3 2
2 0.055468 2 3 3
17 0.055446 2 1 3
8 0.055430 1 2 2
11 0.055291 1 1 3
1 0.055245 3 1 1
3 0.055208 1 3 3
In general: switching wins with prob. 0.666516 and sticking wins with prob. 0.333484
P(switch | chosen 1, revealed 3) =  0.5006998564165546

Uh-huh. It looks like in a specific implementation of this model, with the intel provided by HQ we are equally uncertain about both remaining locations. But averaging over all possible scenarios still gives us the $2:1$ ratio!

So if we're to perform this experiment repeatedly, switching still seems more promising. Indeed the overall probability is:

$$Pr(X\neq L\ | \ R\neq X,\ R\neq L) = \frac{ Pr \left\{ (1,2,3), (2,1,3), (1,3,2), (3,1,2), (2,3,1), (3,2,1) \right\} }{ Pr \left\{ (1,1,3), (1,2,3), (2,1,3), (2,2,3), (1,1,2), (1,3,2), (3,1,2), (3,3,2), (2,2,1), (2,3,1), (3,2,1), (3,3,1) \right\} } = \frac69,$$$$Pr(X\neq L\ | \ R\neq X,\ R\neq L) = \frac23.$$

It is even less intuitive than Monty Hall problem in the sense that in any specific realization our knowledge about both locations is exactly the same. Engaging either target results in success with equal probabilities. And yet in frequentist perspective switching is better!

This definitely has something to do with Simpson's paradox and Gerrymandering.

Variation of parameters

I've been wondering for a while, what kind of logic can lead to the method of variation of parameters (i.e. it's trivial to prove, but why would one ever try to find solution this way).

Now I found a convincing interpretation in the book "Обыкновенные Дифференциальные Уравнения" (ODE) by Arnold This interpretation comes from the celestial mechanics and serves a basis for all of the perturbation methods.

In this book the story for the variation of parameters method begins with a sample model: the planets moving around the sun. The first approximation is the motion according to Kepler's laws. Then the objective is to count deviations, caused by planets attracting each other. And the idea is to suppose that planets would still follow Kepler's laws, but the perturbation would make parameters vary over time.

The same idea applies to the inhomogeneous linear DE's. The solution is \(\phi = \phi_h + \phi_p\) the sum of solution for homogeneous system and particular solution for inhomogeneous one.

Let's suppose that \(\phi_h\) is kind of principal (undisturbed) part of the solution, and \(\phi_p\) is some disturbance caused by inhomogenuity. It could happen that disturbance can be described by variations of constants in \(\phi_h\). Now let's just subtitute such solution into equation: voila! That's the intuition that Zadorozhny's course lacked

(DRAFT) Graphs with integral spectra

Which graphs have integral spectrum?
To read:
  1. Frank Harary, "Which graphs have integral spectra?"
  2. D. Cvetkovic, M. Doob, H. Sachs, "Spectra of Graphs"

Terminology

Todo...
Hereafter, graph means undirected graph without self-loops and parallel edges, specifically
Graph is a pair $(V, E)$, where $V$ is called vertex-set, $E$ is a edge-set, elements of which are two-element subsets of $V$ (unordered pairs) Such unordered pairs are called edges of undirected graph. An edge $e=\{v, w\}$ will further be denoted by $vw$. If there is an edge $vw$, then vertices $v$ and $w$ are said to be adjacent. An edge $vw$ is said to be incident to its vertices, and to be "connecting" them.
But sometimes term can accidentally be used in general (loose) sense, to denote also multidigraphs.
Multigraph is a tuple $(V, E, \phi)$ of two sets, where $V$ is vertex-set, $E$ is edge-set, and $phi$ is a map from $E$ to the set of unordered pairs from $V$. If there is an edge $e\in E$, s.t. $\phi(e) = \{v, w\}$, then vertices $v, w$ are said to be adjacent, and also they are incident with $e$.
(Multi-)digraph is the same with two-element subsets replaced by ordered pairs.
Let $V = (v_1, \ldots, v_n)$. Then Adjacency matrix of (multi-)graph $(V, E)$ is a matrix $(a_{ij})\in\Matr_{n,n}$, where $a_{ij}$ is the number of edges, connecting $v_i$ and $v_j$, i.e. number of edges incident to both $v_i$ and $v_j$
Here, the spectrum of a graph will denote (if not specified) the spectrum of its adjacency matrix.

Rank 1

Let's first consider graphs with adjacency matrix of rank 1. Let $G=(V,E)$ be the graph, $\mathcal A\in\Matr_{n,n}$ be it's adjacency matrix and $A: \RR^n\to\RR^n$ be corresponding (in canonical basis $(e_j), j=\overline{1,n}$ in $\RR^n$) linear mapping. Rank of this operator $A$ (and matrix $\mathcal A$) is $\rank A = \dim\Img A$. If $\rank A = 1$, this operator can be represented in the form $$A x = (x|a) b$$ where $(\cdot|\cdot)$ means dot product, $a\in\RR^n, b\in\Img A$. If $n>1$, then $\dim\Ker A = n - \dim\Img A > 0$ and consequently $0\in\spec A$. Now let's $x\notin\Ker A$. Then $x = \alpha b$, and $$A x = (x|a) b = (\alpha b|a) b = (b|a) \alpha b = (b|a) x$$ Id est, $(b|a)$ is eigenvalue of $A$. Corresponding matrix will be $$\mathcal A = (b_i a_j)_{n\times n} = \begin{pmatrix}b_1 \\ \vdots \\ b_n\end{pmatrix} \begin{pmatrix}a_1 & \cdots & a_n\end{pmatrix} = \begin{pmatrix} a_1 b_1 & \cdots & a_n b_1 \\ \vdots & \ddots & \vdots \\ a_1 b_n & \cdots & a_n b_n \end{pmatrix}$$ because $A e_j = (e_j, a) b = a_j b$.
Summary:

Let $A$ be operator of rank 1, such that $A x = (x|a) b$.
If $n=1$, then $\spec A = \{0\}$.
If $n>1$, then $\spec A = \{0, (b|a)\}$.
  • Graph with adjacency matrix of rank 1 will always have integral spectra
  • If (multi-)graph doesn't have self-loops, then main diagonal is filled with zeros, i.e. $b_i a_i = 0, i=\overline{1,n}$, which means that $(b|a)=0$ and $\spec A$ consists of single point $0$. Together with symmetry restriction, this probably leaves no graphs, except for the trivial one with matrix $(1)$.
  • Enumeration of graphs with such matrices can be reduced to enumeration of vectors $a, b$, so that $b_i a_j = b_j a_i$ (and $b_i a_i = 0$ for graphs without loops).
Probably, the only adjacency matrix of rank 1 which is both symmetric and can be represented in this way is $$\begin{pmatrix} a & \cdots & a \\ \vdots & \ddots & \vdots \\ a & \cdots & a \end{pmatrix}$$ where $a\in\NN$. TODO: proof

Rank 2

There are exact formulas for eigenvalues of an operators of rank two (Dronov, Avilov, "Spectral analysis of operators of rank two"). Linear map of rank two can be (uniquely) represented in the form $$A x = \xi_1(e_1) + \xi_2(e_2)$$ where $\xi_1, \xi_2\in{\RR^n}^\ast = \LB(\RR^n, \RR)$ are linearly independent linear functionals.
Let $A_0 = A|\Img A$ be restriction of $A$ to $\Img A$ and $\mathcal A_0$ be the matrix, corresponding to $A_0$. $$\mathcal A_0 = (a_{ij}) = ( \xi_i(e_j) ) = \begin{pmatrix} \xi_1(e_1) & \xi_1(e_2) \\ \xi_2(e_1) & \xi_2(e_2) \end{pmatrix}$$ If $n>2$, then $0\in\spec A$. Non-zero eigenvalues of $A$ are the roots of charpoly $\chi(\lambda) = \lambda^2 - (a_{11} + a_{22})\lambda + (a_{11}a_{22} - a_{12}a_{21})$ and are given by exact formulas $$\lambda = \frac{1}{2}\left( - (a_{11} + a_{22}) \pm \sqrt{(a_{11} + a_{22})^2 - 4(a_{11}a_{22} - a_{12}a_{21})} \right)$$ where $a_{ij}=\xi_i(e_j)$

In order for this polynomial to have all the roots integer, it should have integer coefficients (always true for adjacency matrices) and $(a_{11} + a_{22})^2 - 4(a_{11}a_{22} - a_{12}a_{21})$ should be a perfect square (i.e. there should be an integer square root).
If $\mathcal A$ is an adjacency matrix, coefficients are all non-negative integer, and $a_{ij} = a_{ji}$. The actual task is to realize conditions for $(a_{11} + a_{22})^2 - 4(a_{11}a_{22} - a_{12}a_{21})$ to be a perfect square.
Note, that $$(a_{11} + a_{22})^2 - 4(a_{11}a_{22} - a_{12}a_{21}) = a_{11}^2 + a_{22}^2 - 2 a_{11}a_{22} + 4 a_{12} a_{21} = (a_{11} - a_{22})^2 + 4 a_{12} a_{21}$$ Let $m = a_{11}- a_{22}$, $p = a_{12} = a_{21}$. Then, the task reduces to finding conditions under which $m^2 + (2p)^2 = k^2$ for some $k$. I.e. it's a question of distribution of pythagorean triples. (TODO)

Now let's consider graphs without self-loops with adjacency matrices of rank 2, consisting only of two vertices. Absence of loops means main diagonal being filled with zeros: $a_{11} = a_{22} = 0$. $$\mathcal A = \begin{pmatrix} 0 & p \\ p & 0 \end{pmatrix}$$ In this case $m=0, k=2p$. And eigenvalues are numbers of the form $\lambda=\pm p$ and $0$ if $n>2$.

TODO: generation of symmetric matrices of dimension $n>2$ and rank 2 and with integer elements

Rank 3