TITLE: Creating zero values in a matrix without following typical Gauss - Jordan steps.
QUESTION [0 upvotes]: I was presented with the following Matrix in an assignment and asked to find the value for B that would  make the rank of the matrix 2.
\begin{pmatrix}3&-3&0\\ 3&-1&2\\ b&0&2\end{pmatrix}
I solved this by using row operations to make the last row all zeros using the following steps.
Step 1: Row 2 = Row 2 - row 1.
\begin{pmatrix}3&-3&0\\ 0&2&2\\ b&0&2\end{pmatrix}
Step 2: Row 3 = Row 3 - Row2.
\begin{pmatrix}3&-3&0\\ 0&2&2\\ b&-2&0\end{pmatrix}
Step 3: Row 3 = Row 3 - 2/3*row1.
\begin{pmatrix}3&-3&0\\ 0&2&2\\ b-2&0&0\end{pmatrix}
From this b must be 2 to make the rank of the matrix 2, no? I was told this was wrong as I had used Gauss-Jordan elimination incorrectly. The answer to the question is two but I was awarded no marks for it. Why is this so wrong? Thank you!

REPLY [1 votes]: Your steps to arrive at the conclusion that the rank is at least $2$ are correct. But you fail to show that the rank is $2$ if and only if $b=2$.
You're only showing that if $b=2$ then the rank is $2$.
Well, you were not far from finishing correctly the argument, but as it stands it's incomplete: the form you get is not triangular. Some row swaps would suffice.
Where's the real problem? You took advantage from the particular matrix, but, as I use to say, you should think to the given matrix as a $1000\times1000$ matrix, maybe with several parameters: you don't want to start looking for promising simplifications, because it would take longer than directly performing Gauss-Jordan.
\begin{align}
\begin{pmatrix}
3 & -3 & 0 \\
3 & -1 & 2 \\
b &  0 & 2
\end{pmatrix}
&\to
\begin{pmatrix}
1 & -1 & 0 \\
3 & -1 & 2 \\
b &  0 & 2
\end{pmatrix}
&& R_1\gets \tfrac{1}{3}R_1
\\[6px]&\to
\begin{pmatrix}
1 & -1 & 0 \\
0 &  2 & 2 \\
0 &  b & 2
\end{pmatrix}
&& \begin{aligned} R_2 &\gets R_2-3R_1 \\ R_3 &\gets R_3-bR_1 \end{aligned}
\\[6px]&\to
\begin{pmatrix}
1 & -1 & 0 \\
0 &  1 & 1 \\
0 &  b & 2
\end{pmatrix}
&& R_2 \gets \tfrac{1}{2}R_2
\\[6px]&\to
\begin{pmatrix}
1 & -1 & 0 \\
0 &  1 & 1 \\
0 &  0 & 2-b
\end{pmatrix}
&& R_3 \gets R_3-bR_2
\end{align}
At this point you have two possibilities: if $b=2$, the elimination stops and the rank is $2$; if $b\ne2$, you have another step and the rank is $3$.


TITLE: Derivative of the measure of the set where $f > t$
QUESTION [5 upvotes]: Let $f$ be a continuous function on a topological measure space $(X,\mu)$. Define $g(t) = \mu\{f \geq t\}$ for $t\in \mathbb R$. I am interested in the derivative of $g$. Is there a simple expression for it? What conditions on $f$ will ensure that it exists almost everywhere? What about everywhere?

REPLY [4 votes]: Perhaps the right question to ask is whether $g$ is absolutely continuous; this is equivalent to $g$ being almost everywhere diferentiable and equal to the integral of its derivative (i.e. the fundamental theorem of calculus holds).
(For a function which is not absolutely continuous, the derivative, even if it exists, is generally not very useful.  For an example with this property, take $X$ to be the Cantor set and $\mu$ the Cantor measure, and $f : X \to \mathbb{R}$ the inclusion function.  Then $g$ is the Cantor function, which is a.e. differentiable but whose derivative is zero.  You can't learn very much about this function from its derivative.)
In your setting, the function $g$ is absolutely continuous if and only if the push-forward measure $\mu \circ f^{-1}$ on $\mathbb{R}$ is absolutely continuous with respect to Lebesgue measure; that is, if for any $A \subset \mathbb{R}$ which has Lebesgue measure zero, we have $\mu(f^{-1}(A))=0$.  (See Wikipedia for references.)
Conditions on $f$ for this to hold can be a bit tricky and will probably require more structure.  For example, in the case where $X = \mathbb{R}^n$ and $\mu$ is a nice smooth measure (e.g. Gaussian measure), a typical condition for $g$ to be absolutely continuous is that $f$ be (weakly) differentiable and $\nabla f \ne 0$ $\mu$-almost everywhere.  (If $X$ is a Banach space and $\mu$ is a Gaussian measure, one can get the same result by means of the Malliavin calculus.)  Is there a particular setting you have in mind?
Edit: You ask about a formula for $g'$.  Let's suppose $X = \mathbb{R}^d$ and $\mu$ is absolutely continuous to Lebesgue measure with $C^1$ density  $p$ (i.e. $d\mu = p dm$).  Also suppose $f$ is, say, $C^1$.  Then, at least formally, we have
$$g'(t) = \int_{\{f > t\}} \left(\nabla \cdot \left(\frac{\nabla f}{|\nabla f|^2}\right) + \frac{\nabla f \cdot \nabla p}{|\nabla f|^2 p}\right)\,d\mu.$$
Proof sketch.  Let $\psi(t) = 1_{[a,b)}(t)$, so $\int_X \psi(f)\,d\mu = g(a) - g(b)$.  Set $\phi(s) = \int_{a}^s \psi(t)\,dt = \int_a^b 1_{\{s > t\}}\,dt$ so that $\phi' = \psi$, and note by the chain rule that $\nabla \phi(f) = \psi(f) \nabla f$.  We thus have
$$\psi(f) = \nabla \phi(f) \cdot \frac{\nabla f}{|\nabla f|^2}$$
and so
$$\begin{align*}
g(a) - g(b) &= \int_X \nabla \phi(f) \cdot \frac{\nabla f}{|\nabla f|^2}\,d\mu \\
&= \int_X \nabla \phi(f) \cdot \frac{\nabla f}{|\nabla f|^2}p \,dm \\
&= -\int_X \phi(f) \left(p \nabla \cdot \left(\frac{\nabla f}{|\nabla f|^2}\right) + \nabla p \cdot \frac{\nabla f}{|\nabla f|^2}\right)\,dm \\
&= -\int_X \phi(f) \left(\nabla \cdot \left(\frac{\nabla f}{|\nabla f|^2}\right) + \frac{\nabla p \cdot \nabla f}{|\nabla f|^2 p}\right)\,d\mu \end{align*}$$
where in the third line we used integration by parts.
If we write $h =   \left(\nabla \cdot \left(\frac{\nabla f}{|\nabla f|^2}\right) + \frac{\nabla p \cdot \nabla f}{|\nabla f|^2 p}\right)$ for short, we have
$$\begin{align*} g(a) - g(b) &= -\int_X \phi(f) h\,d\mu \\
&= -\int_X \int_a^b 1_{\{f > t\}}\,dt\, h\,d\mu \\
&= -\int_a^b \int_X 1_{\{f > t\}} h \,d\mu\,dt  \end{align*}$$
by Fubini's theorem.  Now thanks to the fundamental theorem of calculus we are done.
Of course, one needs to check integrability conditions in several places to make this a real proof, but it does suggest that an essential feature will be that $|\nabla f|$ does not get too close to 0.  I don't know whether this is the kind of formula you are looking for; as I said it suggests that you will need more structure than just a topological measure space.
I took this proof from D. Nualart, The Malliavin Calculus and Related Topics, Proposition 2.1.1.  (There it is in the context of Gaussian measure in infinite dimensions, but the idea is the same.)


TITLE: If $n \geq 1$ is not prime and $x \in\mathbb{Z}_n$ such that $\gcd(x, n) \neq 1$, prove that $x^{n-1} \bmod n \not\equiv 1$.
QUESTION [3 upvotes]: If $n \geq 1$ is not prime and $x \in\mathbb{Z}_n$ such that $\gcd(x, n) \neq 1$, prove that $x^{n-1} \bmod n \not\equiv 1$.

I am not sure why this would be true. So, letting $n$ be a nonprime and $x$ being in $\mathbb{Z}_n$, and with $\gcd(x, n)\neq 1$, both $x$ and $n$ share some common factor. I need to relate this to $x^{n-1}$ having a non-$1$ remainder when divided by $n$, but I don't see any apparent connection that makes this so.
I would really appreciate guidance or clarity, but would not like the problem fully solved for me.

REPLY [3 votes]: Hint $\rm\,\ d\mid x,\,\ d\mid n\mid x^{n-1}\!-\!1\:\Rightarrow\:d\mid 1$


TITLE: Irreducible polynomial
QUESTION [0 upvotes]: I am looking for all irreducible polynomials of degree 5 in $\mathbb{F}_{17}$
with have the form h(y) = $y^5+C$.
I think there aren't any irreducible polynomials of this form because for every C
I can find an element of $\mathbb{F}_{17}$ as a root.
What would be the fastest way to find irreducible polynomials if the form would be h(y) = $y^5$+...

REPLY [2 votes]: You are correct that there no irreducible polynomials of the form $h(y)=y^5+C$ over $\Bbb F_{17}$ because every such polynomial has a root in $\Bbb F_{17}$. An easy way to see this is to notice that $\Bbb F_{17}^*$ is a cyclic group of order 16, which is relatively prime to 5, so that $y \mapsto y^5$ is an automorphism of $\Bbb F_{17}^*$. This means that $y \mapsto y^5$ is a bijection from $\Bbb F_{17}$ to itself, so for any $C$, there exists some $y\in\Bbb F_{17}$ such that $y^5=-C$.
Now, to find an irreducible polynomial of degree 5, a reasonably fast way to do it is to simply pick monic polynomials of degree 5 at random and test them until you find one that is irreducible; about $\frac15$th of them are irreducible (see below), so you probably won't have to try too many.
The question then becomes: how do we test a degree 5 polynomial $f$ for irreducibility? Well, if $f$ is reducible then it must have either a quadratic or a linear factor. Now, the polynomial $x^{17^2}-x=x^{289}-x$ is the product of all irreducible linear and quadratic polynomials over $\Bbb F_{17}$, so we can test for a linear or quadratic factor by checking if $\text{gcd}(f,x^{289}-x) \neq 1$. We can make this easier by recognizing that if we replace $x^{289}-x$ by its reduction mod $f$ then it does not change the gcd with $f$, and we can do this by computing the power $x^{289}$ mod $f$ using repeated squaring. If you're trying to do this by hand, this is still going to require quite a bit of calculation, but on a computer it is very fast and also scales nicely to larger finite fields and higher-degree polynomials (Look up the Ben-Or irreducibility test).
(Proof of the fact that about $\frac15$th of monic degree 5 polynomials are irreducible: $x^{289^5}-x$ factors over $\Bbb F_{17}$ as the product of all of the irreducible polynomials of degree 1 or 5; there are 17 irreducible polynomials of degree 1, so by considering the degree of $x^{17^5}-x$ we conclude that there are $\frac{17^5-17}{5}$ irreducible polynomials of degree 5. So the fraction of all monic degree 5 polynomials that are irreducible is $\frac1{17^5}\cdot \frac{17^5-17}{5} = \frac{1-17^{-4}}5$.)


TITLE: Are a row vector and a column vector the same thing?
QUESTION [7 upvotes]: Suppose I have
$$ A =
\begin{bmatrix}
a\\b\\c\\d\\
\end{bmatrix}$$
$$ B =
\begin{bmatrix}
a& b& c & d\\
\end{bmatrix}$$
Now, I know $A = B^T$. But in what sense are these different mathematical objects?
$$
\begin{bmatrix}
1\\
2\\
3\\
4\\
\end{bmatrix} + \begin{bmatrix}
1\\
2\\
3\\
4\\
\end{bmatrix}= \begin{bmatrix}
2\\
4\\
6\\
8\\
\end{bmatrix}
$$
$$
\begin{bmatrix}
1&2&3&4\\
\end{bmatrix} + \begin{bmatrix}
1&2&3&4\\
\end{bmatrix}= \begin{bmatrix}
2&4&6&8\\
\end{bmatrix}
$$
To me, these seem to behave the same way. Is there any difference between a row vector and a column vector? How are $A$ and $B$ different?

REPLY [2 votes]: Once you declare that you are dealing with matrices, then they must be different: one is $1$ x $4$ and the other is $4$ x $1$. But there is an obvious isomorphism between them: $[a, b, c, d]\rightarrow
\begin{bmatrix}
a\\b\\c\\d\\
\end{bmatrix}$


TITLE: relationship between scalar product and tensor product
QUESTION [0 upvotes]: I've been thinking about different products of vectors and the relationships between them, but am bumping hard into the limits of my knowledge. I was wondering if anyone has any thoughts.
Given two (Euclidean) vectors a and b, we can define a scalar product a.b which gives a scalar of magnitude |a||b|cos t where t is angle between them.
We can also define a tensor product ab whereby we get a matrix whose (ij)th element is the product of the ith element of a and the jth element of b, i.e. (ab)_ij =a_i b_j.
We know that if a and b are perpendicular then a.b=0 and also that Tr(ab)=0.
It seems ike there should be more statement like this which connect the two products, but I am a bit stuck as to what they might be. Does anyone have any thoughts or could anyone point me at some further reading on this?
Many thanks.

REPLY [1 votes]: In fact, if $\mathbf a\otimes\mathbf b$ denotes the tensor product, i.e.
$$
(\mathbf a\otimes\mathbf b)_{ij}:=a_i b_j,
$$
then
$$
\mathbf a\cdot\mathbf b=\sum_{i=1}^na_ib_i=\sum_{i=1}^n(\mathbf a\otimes\mathbf b)_{ii}=\mathrm{Tr} (\mathbf a\otimes\mathbf b)
$$


TITLE: If $h|mn$ and $\gcd(m, n)=1$ then $h=dd^\prime$ where $d|m$ and $d^\prime|n$
QUESTION [0 upvotes]: Assume $m, n \in \mathbb{N}$.
I need to show the theorem in the title as a step in a larger proof about Euler's $\phi$ function.
My steps:
I divided it up to 2 cases:
If $\gcd(h, m) = 1$: Then $h|n$ and $h = 1\times h$.
If $\gcd(h, m) = x > 1$: Mark $h = \alpha x$. We know that $\gcd(x, n) = 1$ because if they share a factor $a > 1$ we get $a|x|m, a|n \Rightarrow $ contradiction to $\gcd(m, n) = 1$.
From here I can quite easily show it using prime decomposition, but I spent a long time searching for a more elegant way to proceed, without using the Fundamental Theorem of Arithmetic. Can you think of such a way? And if so, can you give me a hint for it?
Thank you all in advance :)

REPLY [1 votes]: Hint:  let $d = \gcd(h,m)$ so that $h=d d'$ and $m=dm'$ for integers $d',m'$ with $\gcd(d',m')=1\,$. Then $h \mid mn \iff dd' \mid dm'n \iff d' \mid m'n\,$, but $\,d' \mid m'n \,\land\, \gcd(d',m')=1 \implies d' \mid n\,$.
Note that the hypothesis $\gcd(m,n)=1$ is not used, or necessary.

REPLY [0 votes]: Eventually I figured out a proof without using the Fundamental Theorem of Arithmetic:
Denote $\gcd(m, \alpha ) = u$. $u|m \Rightarrow \gcd(u, n)=1$. $u|\alpha \Rightarrow \alpha = \beta u$.
Now since $\gcd(u, n) = 1$ and $\gcd(x, n) = 1$ we get $\gcd(ux, n) = 1$, and therefore $ux|\beta ux = \alpha x = h|mn \Rightarrow ux|mn \Rightarrow ux|m, ux|h$. Since $x = \gcd(m, h)$ we get $ux|x$ and therefore $u = 1 \Rightarrow \gcd(m, \alpha ) = 1$. At last, we also know that $\alpha | \alpha x = h | mn \Rightarrow \alpha | mn \Rightarrow \alpha | n$ (Since $ \gcd(m, \alpha ) = 1$).
So in conclusion: $h = x \alpha$ where $x|m$ and $\alpha | n$


TITLE: Prove that $\lim\limits_{n \to \infty}\frac{x^n}{n!}=0$
QUESTION [2 upvotes]: Well I can Intuitively see that.
I am wondering If there is a neat way to prove that

REPLY [1 votes]: I more intuitive answer.
$$\lim\limits_{n\to\infty}\frac{x^n}{n!}=\frac{x.x.x.\dots}{1.2.3.\dots}$$.
For some integer $N$, we have $N\leq x<N+1$. Hence, $\lim\limits_{n\to\infty}\frac{x^n}{n!}=\frac{x.x.x.\dots}{1.2.3.\dots}$ is the product of a finite number of real numbers greater than $1$, and an infinite number of real numbers less than $1$. Moreover, the list of real numbers less than $1$ is a strictly decreasing sequence.
So say the product $\frac{x.x.x\dots x}{1.2\dots N}=a$. Then $\lim\limits_{n\to\infty}\frac{x^n}{n!}<a.\left(\frac{x}{N+1}\right)^{n-N}$.
We know that $\frac{x}{N+1}<1$
The limit has to be $0$.


TITLE: Image-preimage adjunction induced from regular epi respects regular monos?
QUESTION [2 upvotes]: Concretely, every set function $f:A\rightarrow B$ induces an adjunction $f_\ast \dashv f^\ast$ between image and preimage. For rings groups, the image and preimage along a surjective ring group homomorphism preserve ideals normal subgroups, which are equalizers of arrows with the arrow that picks out $0$. This is no surprise for $f^\ast$ since it preserves equalizers, but not generally true for $f_\ast$.
Since rings groups are an algebraic theory, the regular epis are precisely the surjective functions. It seems one could just say that regular epis induce image-preimage adjunctions that preserve regular monos.
As pointed out in the comments, the case of rings is not as pleasant because ideals leave the category of rings, so maybe I should replace 'regular' by 'normal'...
At any rate, in which algebraic categories (with zero object) does this hold?

REPLY [1 votes]: Firstly the comments are perhaps misplaced regarding rings since it depends whether or not the definition you use requires a multiplicative identity or not.
For normal epimorphisms and normal monomorphisms this condition has been studied and such categories are called Ideal-determined categories. Any variety of universal algebras that has a unique constant $e$ and for some natural number $n$ one $n+1$-ary term $p(x_1,..,x_n,x_{n+1})$ and $n$ binary terms $s_i(x,y)$ such that $s_i(x,x)=e$ and $p(s_1(x,y),..,s_n(x,y),y)=x$ satisfies this condition. These include the categories of groups, Lie algebras over a field (or even a commuative ring), not necessarily unital rings and many others. It is perhaps worth noting that there are examples that satisfy this condition that do not have such terms.


TITLE: Whatever happened to $L(j)$?
QUESTION [17 upvotes]: So this question probably shows my inner model theoretic ignorance, but:
In "Two remarks on elementary embeddings of the universe" (http://projecteuclid.org/download/pdf_1/euclid.pjm/1102969567), Jech defines - for $j: V\rightarrow M$ a definable-with-parameters elementary embedding - an inner model $L(j)$, and proves that $L(j)$ is the smallest inner model which admits $j$ (in the sense that the inner model thinks $j$ is an elementary embedding as well).
This is a neat, short argument, and the definition of $L(j)$ is very straightforward. Naively, I would suspect that properties of the inner model $L(j)$ would tell us interesting information about the embedding $j$, and similarly for models $L(\overline{j})$ defined for sequences of embeddings $\overline{j}$.
For instance, here's a question which seems natural to me: given an inner model $M\subset V$ and a family of embeddings $j_\eta: V\rightarrow M$ $(\eta\in \kappa)$, it's reasonable to ask for which $I\subset \kappa$ is there an inner model $N$ admitting precisely the $j_\eta$ with $\eta\in I$? In particular, given a left distributive algebra of embeddings, which sub-left distributive algebras can be captured this way? Naively, if I want to capture $\{j_\eta: \eta\in I\}$, my first guess would be to look at $L(\{j_\eta: \eta\in I\})$.
NOTE: this isn't my actual question, I'm just including it to motivate interest in the $L(j)$s.
However, I've never run across these models before, and I can't seem to find any recent reference to them. So, my question is:

Are the $L(j)$s interesting at all from the point of view of modern inner model theory? If not, why not, and if so, why doesn't there seem to be any modern literature about them (maybe they are extremely hard to work with, or maybe there is such literature which I just haven't found yet)?

(For my purposes, "modern" means "since 1990.")

REPLY [6 votes]: I recently noticed that Mitchell returned to $L[j]$ in "Applications of the covering lemma for sequences of measures," where he shows that the model is quite a bit larger than one might expect. The thing is, $L[j]$ isn't $L[E_j]$ where $E_j$ is the short extender of $j$, it's $L[P]$ where $P = \{(x,A) : x\in j(A)\}$ is the entire proper class long extender of $j$. Assuming there is no inner model with a measurable $\kappa$ of order $\kappa^{++}$, Mitchell shows that if $j$ is nontrivial, $L[j]$ contains an iterate of the core model. Moreover, under the same assumption, he proves that if $j$ is the ultrapower embedding associated to a normal ultrafilter, then $L[j]$ satisfies $V = K$. So $L[j]$ contains many measurable cardinals of high order if $K$ does. As far as I know, no one has worked on the question at the level of strong/Woodin cardinals.


TITLE: Showing that rotation about the origin and generally is an isometry
QUESTION [0 upvotes]: Let $ρθ$ be the counterclockwise rotation about the origin $(0, 0)$ through the angle $θ$.
1) Give a proof in the 2-dimensional real plane that $ρθ$ is an isometry.
I am confused if I need to show that $d(p_\theta (x,y), (0,0)) = d((x,y), (0,0)) $ or if I need to pick two different arbitrary points and show that $d(p_\theta (x,y),p_\theta (r,s)) = d((x,y), (r,s)) $.
2) Prove that every general rotation $ρ$ of $R^2$ is an isometry of $R^2$
My thinking for this one is that I would be to show that given a fixed point $(r,s)$ and an arbitrary $(x,y)$, $d(p_\theta (x,y), (r,s)) = d((x,y), (r,s)) $. I'm not sure how to go about proving this.
Any help would be appreciated.

REPLY [0 votes]: 1) An isometry preserves the distance between every pair of points, so you need to show $d(\rho_\theta(P_1),\rho_\theta(P_2))=d(P_1,P_2)$ for an arbitrary pair of points.
2) Decompose the general rotation into a sequence of transformations that you already know to be isometries (you'll use the result from part 1).


TITLE: Induction principle: $(1+x)^{n+1}>1+(n+1)x$
QUESTION [1 upvotes]: Given $(1+x)^{n+1}>1+(n+1)x$ for $x>0$ and for $n$ positive integer.
Putting $n=1$ I get $x^2>0$ so the inductive hypothesis is true.
Putting $n=n+1$ I get $(1+x)^{n+2}>1+(n+2)x$. I can write $(1+x)^{n+2}$ as $(1+x)^n(1+x)^2$ and then I don't know how to go on.

REPLY [0 votes]: No, write
$$(x+1)^{n+2}=(x+1)^{n+1}(x+1)$$ instead of  $$(x+1)^{n+2}=(x+1)^n(x+1)^2.$$
Then you can use the induction hypothesis and
$$(x+1)^{n+1}(x+1)>(1+(n+1)x)(1+x)=1+(n+2)x+x^2>1+(n+2)x.$$

In fact it is easier to start with the equivalent statement
$$(x+1)^n>1+nx$$ for $n>1$.
Then
$$(x+1)^{n+1}>(1+nx)(x+1)>1+(n+1)x$$


TITLE: For $A \in \mathcal{M}_3(\mathbb{C})$, does $\mathrm{tr}(A^2) = \mathrm{tr}(A^3) \in \mathbb{Q}$ imply $\mathrm{tr}(A^4) \in \mathbb{Q}$?
QUESTION [11 upvotes]: Let $A \in \mathcal{M}_3(\mathbb{C})$ such that $\mathrm{tr}(A^2) = \mathrm{tr}(A^3) \in \mathbb{Q},$ where $\mathrm{tr}(A)$ is the trace of $A.$ It is possible to prove that $\mathrm{tr}(A^4) \in \mathbb{Q}?$

REPLY [16 votes]: We fix some $t\in \Bbb C$. Let $a,b,c$ be the complex roots of the equation
$$
X^3-6tX^2+18t^2 X -36 t^3\ .
$$
Let $e_n$ be the elementary symmetric polynomial of degree $n$ in $a,b,c$.
Let $p_n$ be the Newton symmetric polynomial of degree $n$ in $a,b,c$.
By Vieta,
$$\left\{
\begin{aligned}
e_1 &= a+b+c = 6t\ ,\\
e_2 &= ab+bc+ca = 18t^2\ ,\\
e_3 &= abc = 36t^3\ .
\end{aligned}
\right.
$$
Let $A$ be the matrix with diagonal entries $a,b,c$. Then, using the Newton identities,
$$
\begin{aligned}
\operatorname{Trace}(A^2)
&=a^2+b^2+c^2\\
&=p_2\\
&=e_1p_1-2e_2\\
&=6t\cdot 6t-2\cdot 18t^2=0\ ,
\\
\operatorname{Trace}(A^3)
&=a^3+b^3+c^3\\
&=p_3\\
&=e_1p_2-e_2p_1+3e_3\\
&=0-18t^2\cdot 6t+3\cdot 36t^3=0\ ,
\\
\operatorname{Trace}(A^4)
&=a^4+b^4+c^4\\
&=p_4\\
&=e_1p_3-e_2p_2+e_3p_1-4e_4\\
&=0-0+36t^3\cdot 6t-0\\
&=216t^4\ .
\end{aligned}
$$
It is clear that we can chose $t$, such that the last expression is not rational. This gives and explicit counterexample.

Later edit: The general family of cubics with roots $a,b,c$, so that $p_1=p_1(a,b,c)=e_1=e_1(a,b,c)=s$ and $p_2=p_3=p_2(a,b,c)
=p_3(a,b,c)=q$, thus parametrized by $s,q$, is obtained by solving
$$
\begin{aligned}
e_1&=p_1=s\ ,\\
2e_2 &=e_1p_1-p_2=s^2-q\ ,\\
3e_3 &=e_2p_1-e_1p_2+p_3=\frac 12(s^2-q)s-sq+q\ ,\\
\end{aligned}
$$
and $p_4$ is obtained algebraically as $p_4=e_1p_3-e_2p_2+e_3p_1-4e_4$. (Here, $e_4=0$.) The question "It is still possible to find a counterexample so that $s$ (trace of $A$) is a natural (or even rational) number?" has a negative answer. If both $s,q$ are rational, than $p_4$ is rational, as an algebraic expression in $s,q$.


text:
\begin{document}

\title{Receding Horizon Control Based Consensus Scheme in General Linear Multi-agent Systems}

\author{  Huiping~Li,~\IEEEmembership{member~IEEE,}
          Weisheng~Yan

\thanks{
This work was supported by the start-up research fund of the Northwestern Polytechnical University(NPU);
the basic research foundation of NPU with grant no. GEKY 1004.}
\thanks{The authors are with the Department
of Automation, School of Marine Science and Technology, Northwestern Polytechnical University, Xi'an,
710072, China (e-mail: lihuiping@nwpu.edu.cn;peter.huiping@gmail.com).}
}

\maketitle

\begin{abstract}
This paper investigates the consensus problem of general linear multi-agent systems under the framework of optimization.
A novel distributed receding horizon control (RHC) strategy for consensus is proposed.
We show that the consensus protocol generated by the unconstrained distributed RHC can be expressed in an explicit form.
Based on the resulting consensus protocol the necessary and sufficient conditions for ensuring consensus are developed.
Furthermore, we specify more detailed consensus conditions for multi-agent system with general and one-dimensional linear dynamics depending on the difference Riccati equations (DREs), respectively.
Finally, two case studies verify the proposed scheme and the corresponding theoretical results.
\end{abstract}

\begin{IEEEkeywords}
Consensus, receding horizon control (RHC), multi-agent systems, general linear systems, optimization, diagraph.
\end{IEEEkeywords}

\IEEEpeerreviewmaketitle

\section{INTRODUCTION}\label{sec_introduction}
In last two decades, the cooperative control of networked multi-agent systems has received a lot of
attention due to its wide applications. In particular, the consensus problem is of significant importance, and has inspired much progress, e.g., \cite{Reza_04_consensus_TAC,Moreau_05_TAC_consensus,Wei_05_TAC_consensus}.
In this paper, we are interested in solving the consensus problem of multi-agent systems from the distributed optimal control perspective.
The multi-agent system under study is of fixed directed network topology and general linear time invariant (LTI) dynamics associated with each agent.
The objective of this paper is to design a locally optimal consensus strategy for each agent, and further to investigate under what conditions the closed loop system can achieve consensus by the designed strategy.

The optimality of control protocols brings many desired properties such as phase and gain margin, leading to robustness of the closed loop systems.
The core difficulty of the cooperative optimal control for multi-agent systems lies in the fact that the centralized optimization problem cannot generally be distributed among agents, with few exceptions \cite{Cao_08_TSMC_consensus,Movric_14_TAC_optimal_tracking}.
As a result, the best way of circumventing the difficulty is to utilize the locally optimal control strategy and further combine it with regional information exchange scheme to address the system-level interaction and coupling, approximately achieving some global or cooperative behaviors.

In the literature, one approach to the optimal cooperative control is the linear quadratic regulation (LQR) scheme.
For example, the distributed LQR problem of multi-agent systems with LTI dynamics is studied in \cite{Borrelli_08_TAC_distributedLQR},
showing that the overall stability can be guaranteed by appropriately designing the local LQR and using information exchange among network topology.
The consensus problem with optimal Laplacian matrix for multi-agent systems of first-order dynamics is investigated in \cite{Cao_08_TSMC_consensus}, where it is shown that the design of globally optimal Laplacian matrix can only be achieved by properly choosing the global cost function coupled with the network topology.
Recently, the LQR-based consensus problem of multi-agent systems with LTI dynamics and fixed directed topology is addressed in \cite{Movric_14_TAC_optimal_tracking}, indicating that the globally optimal consensus performance can be achieved by using locally optimal consensus protocol if and only if the overall performance index is selected in a special form depending on the graph structure.

Another way of achieving the (sub-)optimal cooperative control of multi-agent systems is the distributed receding horizon control (RHC) strategy, also known as distributed model predictive control. Based on this approach, there have been many results developed for cooperative stabilization, formation control, and its applications. For example, the distributed RHC-based scheme for cooperative stabilization is proposed in \cite{Dunbar_06_Auto_DMPC,Muller_12_DMPC_IJRNC}, and the formation stabilization is addressed in \cite{Keviczky_06_auto_DMPC} and its application is reported in \cite{Keviczky_08_TCST_formation_MPC}.
Furthermore, the robust distributed RHC problems that can be used for cooperative stabilization are studied in \cite{Richards_IJC_07_RDMPC} for linear systems with coupled constraints and in \cite{Li_TAC_14_RDRHC} for nonlinear systems. To further attack the unreliability of the communication networks, the cooperative stabilization problem of multi-agent nonlinear systems with communication delays are investigated in \cite{Li_SCL_DMPC_14,Franco_08_TAC_DMPC,Li_Auto_14_DRHC}. Note that all of these results use cost functions as Lyapunov functions to prove stability.

Even though it is very desirable to achieve optimal consensus by distributed RHC scheme, there have been few results for the consensus problem of multi-agent systems due to the difficulty that the cost function may not be directly used as Lyapunov function.
In \cite {Ferrari_09_TAC_MPC_consensus}, Ferrari-Trecate {\em et al.} study the consensus problem of multi-agent systems of first-order and second-order dynamics, and the sufficient conditions for achieving consensus are developed by exploiting the geometry properties of the optimal path. Zhan {\em et al.} investigate the consensus problem of first-order sampled-data multi-agent systems in \cite {Zhan_13_auto_consensus}, where state and control input information needs to be exchanged. Note that these two results are only focused on special type of linear systems, which is of limited use.
In \cite{Johansson_08_auto_optimal_consensus} Johansson {\em et al.} propose to use the negotiation to reach the optimal consensus value by implementing the primal decomposition and incremental sub-gradient algorithm, but the effect of the network topology is not explicitly considered.

It can seen that the receding horizon control -based consensus scheme for multi-agent systems with general LTI dynamics has not been solved, and the relationship between consensus and the interplay between the network topology and the RHC design is still unclear, which motivates this study. The main contribution of this paper is two-fold.
\begin{itemize}
\item A novel distributed RHC strategy is proposed for designing the consensus protocol.
      In this strategy, each agent at each time instant only needs to obtain its neighbors's state once via communication network, which is more efficient than the work in \cite{Li_TAC_14_RDRHC,Dunbar_06_Auto_DMPC} (where the state and its predicted trajectory need to be transmitted) and \cite{Muller_12_DMPC_IJRNC,Zhan_13_auto_consensus} (where the neighbors' information needs to be exchanged for many times at each time instant). In addition, we show that the consensus protocol generated by the RHC is a feedback of the linear combination of each agent's state and its neighbors' states, and the feedback gains depend on a set of difference matrix equations. We believe our results partially extend the results in \cite{Ferrari_09_TAC_MPC_consensus,Zhan_13_auto_consensus} to multi-agent systems with LTI dynamics.
\item Given the proposed distributed RHC strategy, a necessary and sufficient condition for ensuring consensus is developed. We show that the consensus can be reached if and only if the network topology contains a spanning tree and a simultaneous stabilization problem can be solved. Furthermore, more specifical sufficient consensus conditions depending on one Reccati difference equation for the multi-agent with LTI dynamics and one-dimensional linear dynamics are also developed, respectively.
\end{itemize}

The remainder of this paper is organized as follows.
Section \ref{Sec_problem_formulation} introduces some well-known results from graph theory and formulates the problem to be studied.
Section \ref{Sec_consensus_protocol} presents the novel distributed RHC scheme, and develops a detailed consensus protocol.
The necessary and sufficient conditions for enuring consensus are proposed in Section \ref{sec_consensus_analysis}, and more specifical sufficient consensus conditions for multi-agent systems with LTI dynamics and one-dimensional linear dynamics are also reported in this section. The case studies are demonstrated in Section \ref{Sec_simulation}.
Finally, the conclusion remarks are summarized in Section~\ref{Sec_Conclusion}.

For the ease of presentation, the following notations are adopted in this paper.
The symbol $\mathbb{R}$ represents the real space.
For a real matrix $A$, its transposition and inverse (if the inverse exists) are denoted as ``$A^{\rm T}$'' and ``$A^{-1}$'', respectively.
If $A$ is a complex matrix, then the transposition is denoted by $A^{\rm H}$.
Given a real (or complex) number $\lambda$, the absolute value (modulus) is defined as $|\lambda|$.
Given a matrix (or a column vector) $X$ and another matrix $P$ with appropriate dimension,
the $2$-induced norm (or the Euclidean norm) of $X$ is denoted by $\|X\|$ and the $P$-weighted norm of $X$
is denoted by $\|X\|_{P} \triangleq \sqrt{X^{\rm T}PX}$.
Given matrix $Q$, $Q>0$ ($Q\geqslant0$) stands for the matrix $Q$ being positive definite (semi-positive definite).
Define the column operation ${\rm col}\{x_1,x_2,\cdots,x_n\}$ as
$[x_1^{\rm T},x_2^{\rm T},\cdots,x_n^{\rm T}]^{\rm T}$, where $x_1, x_2,\cdots,x_n$ are column vectors.
$I_n$ stands for the identity matrix of dimension $n$,
and $\textbf{1}_n$ represents an $n$-dimensional column vector $[1, \cdots, 1]^{\rm T}$.
The symbol $\otimes$ stands for the Kronect product.

\section{Problem Formulation}\label{Sec_problem_formulation}
Consider a multi-agent system of $M$ linear agents. For each agent $i$, the dynamics is described as
\begin{equation}\label{equ_each_agent}
x_i(k+1) = A x_i(k) + B u_i(k),
\end{equation}
where $x_i(k+1) \in \mathbb{R}^{n}$ is the system state,
and $u_i(k) \in \mathbb{R}^m$ is the control input of agent $i$.

There exists a communication network among the $M$-agent system, and the network topology is described as a
directional graph (diagraph) $\mathcal{G} \triangleq \{\mathcal{V},\mathcal{E},\mathcal{A}\}$.
Here, $\mathcal{V} = \{i, i = 1,\cdots,M\}$ is the collection of the nodes of the digraph representing each agent $i$,
$\mathcal{E} \subset \mathcal{V}\times \mathcal{V}$ denotes the edges of paired agents, and $\mathcal{A} =[a_{ij}]\in\mathbb{R}^{M\times M}$ is the adjacency matrix with
$a_{ij}\geqslant 0$. If there is a connection from agent $i$ to $j$, then $a_{ij} = 1$; otherwise, $a_{ij} = 0$. We assume there is no self-circle in the diagraph $\mathcal{G}$, i.e., $a_{ii} = 0$. For each agent $i$, its neighbors are denoted by the agents from which it can obtain information, and the index set for agent $i$'s neighbors is denoted as $\mathcal{N}_i \triangleq \{j|(i,j)\subset \mathcal{E}\}$. The number of agents in $\mathcal{N}_i$ is denoted as $|\mathcal{N}_i|$.
The in-degree of agent $i$ is denoted as $Deg_{in}(i) = \sum_{i=j}^M a_{ij}$, and the degree matrix is denoted as $\mathcal{D}={\rm diag}\{Deg(1),\cdots, Deg (M)\}$. The Laplacian matrix of $\mathcal{G}$ is denoted as $\mathcal{L} = \mathcal{D} - \mathcal{A}$.
Arrange the eigenvalues of $\mathcal{L}$ as $|\lambda_1| \leqslant |\lambda_2| \leqslant \cdots \leqslant |\lambda_M|$.
Assume that the diagraph $\mathcal{G}$ is fixed. Firstly, we recall some standing results from the graph theory \cite{Wei_05_TAC_consensus,Reza_04_consensus_TAC,You_11_TAC_consensus}.

\begin{lemma}\label{lem_spanning_tree}
The digraph $\mathcal{G}$ contains a spanning tree if and only if zero is a simple eigenvalue of the Laplacian matrix $\mathcal{L}$, i.e.,
$0 < |\lambda_2| \leqslant \cdots \leqslant |\lambda_M|$, and the corresponding right eigenvector is ${\rm \textbf{1}}$.
\end{lemma}

For the linear system in (\ref{equ_each_agent}), a standing assumption is made: The pair $[A,B]$ is controllable.
We assume that at each time instant $k$, over the given communication network,
agent $i$ can get state information $x_j(k)$, $j\in\mathcal{N}_i$ from its neighbors.
The communication network is reliable and the information can be transmitted instantaneously without time consumption.

\begin{definition}\cite{You_11_TAC_consensus}
The discrete-time multi-agent system in (\ref{equ_each_agent}) with a given network topology $\mathcal{G}$, and under a distributed control protocol
$u_i(k) = f(x_i(k), x_{-i}(k))$, is said to achieve consensus if,
\begin{equation*}
\lim_{k \rightarrow \infty } \|x_i(k) - x_j(k) \| = 0, j = 1, \cdots, M,
\end{equation*}
where $x_{-i}(k)$ are the collection of agent $i$'s neighbors' states, i.e., $x_{-i}(k) \triangleq \{x_j,j\in\mathcal{N}_i\}$ and $f: \underbrace{\mathbb{R}^n \times \cdots\times \mathbb{R}^n}_{|\mathcal{N}_i| + 1}\rightarrow \mathbb{R}^m$.
\end{definition}
In this paper, we are interested in designing $u_i(k) = f(x_i(k), x_{-i}(k))$ using the distributed RHC strategy for each agent $i$ to achieve consensus.

\section{Distributed RHC based Consensus Protocol}\label{Sec_consensus_protocol}
This section first presents the distributed RHC based consensus strategy, and then develops the detailed consensus protocols for each agent.
\subsection{Distributed RHC Scheme}
For each agent $i$, we propose to utilize the following optimization problem to generate the consensus protocol.
\begin{problem}
\begin{align*}
U_i^*(k) = \arg\min_{\hat{U}_i(k)} J_i(\hat{x}_i(k),\hat{U}_i(k),x_{-i}(k))
\end{align*}
subject to
\begin{align*}
\hat{x}_i(k+n+1|k) = A \hat{x}_i(k+n|k) + B \hat{u}_i(k+n|k),
\end{align*}
where $n = 0, \cdots, N-1$.
Here, $\hat{x}_i(k|k) = x_i(k)$, $\hat{U}_i(k)= \{ \hat{u}_i(k|k), \cdots, \hat{u}_i(k+N-1|k)\}$ and $J_i(\hat{x}_i(k),\hat{U}_i(k),x_{-i}(k)$ is defined as
\begin{align}
  & J_i(\hat{x}_i(k),\hat{U}_i(k),x_{-i}(k))\nonumber\\
= &\sum_{n=0}^{N-1} \left(\|\hat{u}_i(k+n|k)\|_{R_i}^2 + \sum_{j\in \mathcal{N}_i}a_{ij}\|\hat{x}_i(k+n|k) - x_j(k)\|_{Q_i}^2\right)\nonumber\\
  & + \sum_{j\in \mathcal{N}_i}a_{ij}\|\hat{x}_i(k+N|k) - x_j(k)\|_{Q_{iN}}^2,
\end{align}
where $R_i>0$, $Q_i>0$ and $Q_{iN}>0$ are symmetric matrices, and $N>0$ is a positive integer which is called the prediction horizon.
\end{problem}

At each time instant $k$, each agent gets its neighbors' state information $x_j(k)$, $j\in\mathcal{N}_i$, solves Problem 1 and then uses $u^*_i(k|k)$ as the control input to achieve consensus.
\begin{remark}
In Problem 1, we use the term $\sum_{j\in \mathcal{N}_i}a_{ij}\|\hat{x}_i(k+n|k) - x_j(k)\|_{Q_i}^2$ to achieve consensus. Note that the consensus term can be rewritten as $|\mathcal{N}_i|\|\hat{x}_i(k+n|k) - ave(x_{-i}(k))\|_{Q_i}^2$, where $ave(x_{-i}(k))$ is the average of agent $i$'s neighboring states, which is consistent with the consensus term in \cite{Ferrari_09_TAC_MPC_consensus}. However, Problem 1 generates the first-order and second-order cases in \cite{Ferrari_09_TAC_MPC_consensus} to general linear systems. In addition, the solve of Problem 1 only requires the exchange of agent $i$ neighbors' state for one time, which results in less communication load in comparison with these in \cite{Muller_12_DMPC_IJRNC,Zhan_13_auto_consensus}, where more information is needed to exchange for consensus.
\end{remark}

\subsection{Specific Consensus Protocol}
This subsection shows that the consensus protocol generated by solving Problem 1 is can be expressed in an explicit form.
By using the convex optimization approach, the result is reported in the following theorem.
\begin{theorem}\label{thm_consensus_law}
For the system in (\ref{equ_each_agent}) with network topology $\mathcal{G}$ and the optimization problem 1, the optimal solution is given as:
\begin{equation*}
\hat{u}_i^*(k+n|k) = \sum_j^{M} a_{ij} [K_i(n) \hat{x}_i(k+n|k) + G_i(n) x_j(k)],
\end{equation*}
Here, $n = 0,\cdots,N-1$, $K_i(n) = -R^{-1}_i B^{\rm T} [I + \sum_{j=1}^{M}a_{ij} P_i(n+1)B R^{-1}_iB^{\rm T}]^{-1} P_i(n+1) A$, and
$G_i(n) = -R^{-1}_i B^{\rm T} [I + \sum_{j=1}^{M}a_{ij} P_i(n+1)B R^{-1}_i B^{\rm T}]^{-1} \Delta_i(n+1)$,
where $P_i(n+1)$ and $\Delta_i(n+1)$ satisfy the following matrix equations, respectively:
\begin{align}
P_i(n) = & A^{\rm T}[I + \sum_{j=1}^{M}a_{ij} P_i(n+1)B R^{-1}_i B^{\rm T}]^{-1}P_i(n+1)A + Q_i,\label{equ_Pn} \\
\Delta_i(n) =& A^{\rm T}[I + \sum_{j=1}^{M}a_{ij} P_i(n+1)B R^{-1}_i B^{\rm T}]^{-1}\Delta_i(n+1) -Q_i,\label{equ_Deltan}
\end{align}
with the initial conditions $P_i(N) = Q_{iN}$ and $\Delta_i(N) = -Q_{iN}$.
Furthermore, the consensus protocol for each agent $i$ is given as:
\begin{equation}\label{equ_consensus_law}
u_i(k) = u_i^*(k|k).
\end{equation}
\end{theorem}

\begin{proof}
By introducing the lagrange multipliers $\lambda_i(n+1) \in \mathbb{R}^n, n = 0, \cdots, N-1$, construct a lagrange function as
\begin{align*}
L(\hat{U}_i(k),\hat{X}_i(k)) \triangleq & \frac{1}{2} J_i(\hat{x}_i(k),\hat{U}_i(k),x_{-i}(k)) \\
                               & + \sum_{n=0}^{N-1}\lambda^{\rm T}_i(n+1)[A\hat{x}_i(k+n|k)\nonumber \\
                               &  + B \hat{u}_i(k+n|k) - \hat{x}_i(k+n+1|k)],
\end{align*}
where $\hat{X}_i(k) \triangleq \{\hat{x}_i(k|k),\cdots,\hat{x}_i(k+N-1|k)\}$.
Since $Q_i>0, Q_{iN}>0$ and $R_i>0$, the objective function is strictly convex. According to the the Karush-Kuhn-Tucker (KKT) conditions \cite{Lu_12_optimization}, there exists a unique global minima for Problem 1, which satisfies the following conditions:
\begin{align}
\frac{\partial L}{\partial \hat{x}_i^*(k+n|k)} = & \sum_{j=1}^{M} Q_i a_{ij}[\hat{x}_i^*(k+n|k)-x_j(k)]+ A^{\rm T} \lambda_i(n+1) - \lambda(n) = 0,\label{equ_KKT1} \\
\frac{\partial L}{\partial \hat{x}_i^*(k+N|k)} = & \sum_{j=1}^{M} Q_{iN} a_{ij}[\hat{x}_i^*(k+N|k)-x_j(k)]- \lambda_i(N) = 0,\label{equ_KKT2}\\
\frac{\partial L}{\partial \hat{u}_i^*(k+n|k)} & = R_i \hat{u}_i^*(k+n|k) + B^{\rm T} \lambda_i(n+1) = 0,\label{equ_KKT3}\\
A\hat{x}_i^*(k+n|k)& + B \hat{u}_i^*(k+n|k) - \hat{x}_i^*(k+n+1|k) = 0,\label{equ_KKT4}
\end{align}
where $n = 0, \cdots, N-1$.

In what follows, we first show an equation to evaluate $\lambda_i(n)$, by mathematical induction as follows:
\begin{equation}\label{equ_lamdai}
\lambda_i(n) = \sum_{j=1}^{M} [P_i(n) \hat{x}_i^*(k+n|k) + \Delta_i(n) x_j(k)],
\end{equation}
where, $ n = N, \cdots, 0$.
Using (\ref{equ_KKT3}), we can get
\begin{equation}\label{equ_u_k}
\hat{u}_i^*(k+n|k) = -R_i^{-1} B^{\rm T} \lambda_i(n+1).
\end{equation}
When $n=N$, from (\ref{equ_KKT2}), we can obtain that
\begin{align*}
\lambda_i(N) = & \sum_{j=1}^{M} a_{ij}Q_{iN}[\hat{x}_i^*(k+N|k)-x_j(k)]\nonumber\\
             = & \sum_{j=1}^{M} a_{ij}[P_i(N)\hat{x}_i^*(k+N|k) + \Delta_i(N) x_j(k)].
\end{align*}
Assume that (\ref{equ_lamdai}) holds for some $n = l+1$ with $ l \leqslant N-1$.
When $n = l$, by combining (\ref{equ_KKT1}), (\ref{equ_KKT4}) and (\ref{equ_u_k}), we have
\begin{align*}
\lambda_i(l) = & A^{\rm T} [I + \sum_{j=1}^{M}a_{ij} P_i(n+1)B R^{-1}_i B^{\rm T}]^{-1}\nonumber\\
               & \times [\sum_{j=1}^{\rm M} a_{ij} (P_i(l+1) A\hat{x}_i^*(k+n|k)+ \Delta_i(l+1) x_j(k))]\nonumber\\
               &  + \sum_{j=1}^{M} a_{ij} Q_i(\hat{x}_i^*(k+n|k) - x_j(k))\nonumber\\
=& \sum_{j=1}^{M} a_{ij}[P_i(l) \hat{x}_i(k+n|k) + \Delta_i(l) x_j(k)].
\end{align*}
Therefore, using the mathematical induction, (\ref{equ_lamdai}) has been proven.
Finally, the result in Theorem \ref{thm_consensus_law} follows by plugging (\ref{equ_lamdai}) into (\ref{equ_u_k}).
This completes the proof.
\end{proof}

Note that $P_i(n)$ satisfies a modified Reccati difference equation in (\ref{equ_Pn}), which depends on the network topology.
In order to decouple (\ref{equ_Pn}) from the network topology, we design $R_i$ such that
\begin{equation}\label{equ_design_R}
R_1/|\mathcal{N}_1| = \cdots = R_M/|\mathcal{N}_M| = R,
\end{equation}
where $R>0$. Using (\ref{equ_design_R}), (\ref{equ_Pn}) and (\ref{equ_Deltan}) become
\begin{align}
P_i(n) = A^{\rm T}[I + P_i(n+1)B R^{-1} B^{\rm T}]^{-1}P_i(n+1)A + Q_i,\label{equ_RDE_Pn} \\
\Delta_i(n) = A^{\rm T}[I + P_i(n+1)B R^{-1} B^{\rm T}]^{-1}\Delta_i(n+1) -Q_i.\label{equ_RDE_Deltan}
\end{align}
Therefore, $P_i(n)$ follows a standard RDE in (\ref{equ_RDE_Pn}).

\section{Consensus Analysis}\label{sec_consensus_analysis}
This sections first develops a necessary and sufficient condition for achieving consensus of general linear agent systems, then further propose the sufficient conditions for multi-agent system of general LTI and one-dimensional dynamics, respectively.
\subsection{Necessary and Sufficient Condition}
The necessary and sufficient condition for reaching consensus is as follows.
\begin{theorem}\label{thm_iff}
For the system in (\ref{equ_each_agent}) with the network topology $\mathcal{G}$ and the consensus protocol in (\ref{equ_consensus_law}), assume that $R_i$ is designed as in (\ref{equ_design_R}). Then the consensus can be reached if and only if (a) $\mathcal{G}$ contains a spanning tree, and (b) $A-BK_i + (\lambda_i - 1)B G_i$ is stable for all $\lambda_i$, $i=2,\cdots, M$, where $\lambda_i$ are the nonzero eigenvalues of $\Gamma$ defined as $\Gamma = {\rm diag}(1/|\mathcal{N}_1|, \cdots, 1/|\mathcal{N}_M|) \mathcal{L}$, and
\begin{align*}
K_i \triangleq &  -R^{-1}B^{\rm T} [I + P_i(1) B R^{-1} B^{\rm T}]^{-1} P_i(1) A\\
G_i \triangleq &  -R^{-1}B^{\rm T}[I + P_i(1) B R^{-1} B^{\rm T}]^{-1} \Delta_i(1).
\end{align*}
\end{theorem}

Before proving Theorem \ref{thm_iff}, a lemma is first needed.
\begin{lemma}\label{lemma_new_graph}
If the graph $\mathcal{G}$ contains a spanning tree, then a new graph $\tilde{\mathcal{G}} \triangleq \{\mathcal{V}, \mathcal{E}, \tilde{\mathcal{A}}\}$ also contains a panning tree, with $\sum_{j=1}^{M} \tilde{a}_{ij} = 1$ for all $i$, and the corresponding Laplacian matrix is $\Gamma$, where $\tilde{\mathcal{A}} = {\rm diag}(1/|\mathcal{N}_1|, \cdots, 1/|\mathcal{N}_M|) \mathcal{A}$.
\end{lemma}

The proof of lemma \ref{lemma_new_graph} is straightforward, so it is omitted here.

\begin{proof}
For each agent $i$, plugging the consensus law in (\ref{equ_consensus_law}) into (\ref{equ_each_agent}), and doing some algebraic operations, we have
\begin{align*}
x_i(k+1) = A x_i(k) - \sum_{j=1}^{M}\tilde{a}_{ij}(B K_i x_i(k) + B G_i x_j(k)),
\end{align*}
where $\tilde{a}_{ij}$ is the element in $\tilde{\mathcal{A}}$.
Define $\delta_i(k) = x_i(k) - x_1(k)$, and we have
\begin{align*}
\delta_i(k) = (A-BK_i) \delta_i(k) - \sum_{j=1}^{M}(\tilde{a}_{ij}-\tilde{a}_{1j}) B G_i \delta_j(k),
\end{align*}
where $i = 2, \cdots, M$.
By writing the above equations in an augmented form, one gets
\begin{align*}
& \delta(k+1) = (I_{M-1}\otimes(A-BK_i))\delta(k)\nonumber\\
&  - \left[\left(
                                                    \begin{array}{ccc}
                                                      \tilde{a}_{22}- \tilde{a}_{12} & \ldots & \tilde{a}_{2M}- \tilde{a}_{1M}\\
                                                      \vdots & \ddots & \vdots \\
                                                      \tilde{a}_{M2}- \tilde{a}_{12} & \ldots & \tilde{a}_{MM}- \tilde{a}_{1M} \\
                                                    \end{array}
                                                  \right)
\otimes (BG_i)\right]\delta(k),
\end{align*}
where $\delta(k) = {\rm col}(\delta_2(k), \cdots, \delta_M(k))$. The above equation can be further written as
\begin{align}\label{equ_closed_A_delta}
\delta(k+1) = A_\delta \delta(k)
\end{align}
where $A_\delta = (I_{M-1}\otimes(A-BK_i))+ (\tilde{\mathcal{L}}_p + \textbf{1}_{M-1} \tilde{a}_1^{\rm T} \otimes B G_i) - (I_{M-1}\otimes B G_i)$, and $ \tilde{\mathcal{L}}_p = \left[
                                                    \begin{array}{cccc}
                                                      1 & -\tilde{a}_{22} &  \ldots & \tilde{a}_{2M}\\
                                                      -\tilde{a}_{32} & 1 & \ldots &  -\tilde{a}_{3M}\\
                                                      \vdots & \vdots & \ddots & \vdots \\
                                                      -\tilde{a}_{M2} & -\tilde{a}_{M3} & \ldots & 1\\
                                                    \end{array}
                                                  \right]$ and $\tilde{a}_1 = [\tilde{a}_{12}, \cdots, \tilde{a}_{1M}]^{\rm T}$.
From (\ref{equ_closed_A_delta}), it can be seen that the consensus can be reached if and only if all the eigenvalues of $A_\delta$ are in the unit circle. Next, we need to analyze the properties of the eigenvalues of $A_\delta$.
According to Lemma \ref{lemma_new_graph} and Lemma \ref{lem_spanning_tree}, $\Gamma$ has exactly one zero eigenvalue. Put the nonzero eigenvalues of $\Gamma$ in order as $|\lambda_2|\leqslant \cdots \leqslant |\lambda_M|$. Since $S^{-1} \Gamma S = \left[
                           \begin{array}{cc}
                             0 & -\tilde{a}_1^{\rm} \\
                             0 & \tilde{\mathcal{L}}_p + \textbf{1}_{M-1} \tilde{a}_1^{\rm T} \\
                           \end{array}
                         \right]
$, the eigenvalues of $\tilde{\mathcal{L}}_p + \textbf{1}_{M-1} \tilde{a}_1^{\rm T}$ are $\lambda_2, \cdots, \lambda_M$.
Therefore, there exists a nonsingular matrix $T$, such that
\begin{align*}
T^{-1}(\tilde{\mathcal{L}}_p + \textbf{1}_{M-1} \tilde{a}_1^{\rm T} ) T = J = {\rm \diag}(J_1, \cdots, J_s),
\end{align*}
where $J_k$, $k=1,\cdots, s$ are upper triangular Jordan blocks and the principle diagonal elements are $\lambda_2, \cdots, \lambda_M$.
As a result, we have
\begin{align*}
& (T\otimes I_n)^{-1} A_\delta (T\otimes I_n) \nonumber \\
= & I_{M-1}\otimes(A-BK_i) + J\otimes B G_i - I_{M-1} B G_i.
\end{align*}
Thus, the eigenvalues of $A_\delta$ are $A-BK_i + (\lambda_i -1) B G_i$, for all $i = 2, \cdots, M$.
That is, the consensus can be reached if and only if $A-BK_i + (\lambda_i -1) B G_i$ are stable.
The proof is completed.
\end{proof}

Note that $K_i$ and $G_i$ depends on the matrix equations in (\ref{equ_RDE_Pn}) and (\ref{equ_RDE_Deltan}), respectively.
In particular, the (\ref{equ_RDE_Deltan}) is not a RDE, and thus might be of complex properties. In the following, we develop more detailed sufficient conditions to facilitate design.
\subsection{Sufficient Conditions for General Linear Systems}
In this section, we develop sufficient conditions for ensuring consensus, which are reported as follows.
\begin{theorem}\label{col_sufficient_LTI}
For the system in (\ref{equ_each_agent}) with the network topology ${\mathcal{G}}$, assume that ${\mathcal{G}}$ contains a spanning tree, and $R_i$ is designed as in (\ref{equ_design_R}). If $Q_{iN}$ and $Q_i$ are designed such that
\begin{align}
&  Q_{iN} - P_i(N-1) >0, \label{equ_monotically_P}\\
& Q_i - \Xi_i  -\|\lambda_j-1\|^2\nonumber\\
&\times \|I + B(R+B^{\rm T}PB)^{-1}B^{\rm T}\|_{[\bar{\rho}^{N-1}_i Q_{iN} + \sum_{l=1}^{N-2}\bar{\rho}_i^l Q_i]}^2 > 0,\label{equ_sufficient_Q}
\end{align}
where $\Xi_i \triangleq \| B(R + B^{\rm T} P_i(1) B)^{-1}B^{\rm T} P_i(1) \bar{A}_i\|^2$, $\bar{A}_i = A - BK_i$, $\bar{\rho}_i = \rho(A^{\rm T}(I + P_i(1) B R^{-1}B)^{-1})$ and $\lambda_j$, $j=2, \cdots, M$, are the eigenvalues of $\tilde{\mathcal{L}}$.
\end{theorem}

Before developing the proof of Theorem \ref{col_sufficient_LTI}, three lemmas are needed.
\begin{lemma}\label{lemma_RDE}
For the RDE in (\ref{equ_RDE_Pn}), if $Q_{iN} - P_i(N-1)>0$, then $ P_i(N)>\cdots, >P_i(1)$, and $\hat{u}_i^*(k+n|k) = BK_i(k+n|k)$ is a stabilizing controller law for the system in (\ref{equ_each_agent}), $n = N-1, \cdots, 0$.
\end{lemma}
The proof can be directly followed using Theorem 1 and Lemma 1 in \cite{Poubelle_88_TAC_FakeReccati} by considering $Q_i>0$.
\begin{lemma}\label{lemma_special_G_i}
For the RDE in (\ref{equ_RDE_Pn}) and all the eigenvalues $\lambda_2, \cdots, \lambda_M$ of $\tilde{\mathcal{L}}$, the following holds:
\begin{align}\label{equ_temp_Pi(1)}
& P_i(1) -(A- \lambda_i B K_i)^{\rm H} P_i(1)(A- \lambda_i B K_i) \nonumber\\
> & (1-\bar{\lambda}_i)P_i(1) + (\bar{\lambda}_i - 1)A^{\rm T}P_i(1)A + \bar{\lambda} Q_i,
\end{align}
where $\bar{\lambda}_i = \lambda_i^{\rm H} + \lambda_i - \|\lambda_i\|^2$.
\end{lemma}
\begin{proof}
According to \cite{Anderson_71_LOC}, $K_i$ can also been written as
\begin{equation}\label{equ_K_i_newform}
K_i = (R + B^{\rm T} P_i(1) B)^{-1}B^{\rm T} P_i(1) A.
\end{equation}
Using (\ref{equ_K_i_newform}), we have
\begin{align*}
  & P_i(1) - (A- \lambda_i B K_i)^{\rm H} P_i(1)(A- \lambda_i B K_i) \nonumber\\
= & P_i(1) - A^{\rm T} P_i(1)A + (\lambda_i^{\rm H} + \lambda_i) A^{\rm T} P_i(1)\nonumber\\
  &\times  B (R+ B^{\rm T}P_i(1)B)^{-1}B^{\rm T} P_i(1)A \nonumber\\
& - \|\lambda_i\|^2  A^{\rm T} P_i(1) B (R+ B^{\rm T}P_i(1)B)^{-1}\nonumber \\
&\times B^{\rm T} P_i(1) B (R + B^{\rm T} P_i(1) B)^{-1} B^{\rm T} P_i(1) A\nonumber\\
\geqslant & P_i(1) - A^{\rm T} P_i(1)A \nonumber\\
& + \bar{\lambda_i} A^{\rm T} P_i(1) B (R+ B^{\rm T}P_i(1)B)^{-1}B^{\rm T} P_i(1)A.
\end{align*}
The DRE in (\ref{equ_RDE_Pn}) can also be written as
\begin{align*}
P_i(n) = & Q_i + A^{\rm T} P_i(n+1) A - A^{\rm T} P_i(n+1) B\nonumber\\
&\times (R+ B^{\rm T}P_i(n+1)B)^{-1}B^{\rm T} P_i(n+1)A.
\end{align*}
Therefore, we further have
 \begin{align*}
  & P_i(1) - (A- \lambda_i B K_i)^{\rm H} P_i(1)(A- \lambda_i B K_i) \nonumber\\
\geqslant & P_i(1) - A^{\rm T} P_i(1)A + \bar{\lambda_i} (Q_i + A^{\rm T} P_i(1) - P_i(0)).
\end{align*}
According to Lemma \ref{lemma_RDE}, it can be derived that $P_i(0) < P_i(1)$.
As a result, (\ref{equ_temp_Pi(1)}) follows. This completes the proof.
\end{proof}
The following lemma gives a bound of the sequence $\{\Delta_i(n)\}$.
\begin{lemma}\label{lemma_delta_auxiliary}
For any positive definite matrix $\Pi\in \mathbb{R}^{n\times n}$, the following holds:
\begin{equation*}
\|\Pi\|^2_{\Delta_i(n)} \leqslant \|\Pi\|^2_{\bar{\rho}^{N-n}_i Q_{iN} + \sum_{l=1}^{N-(n+1)}\bar{\rho}_i^l Q_i},
\end{equation*}
where $n = N, \cdots, 0$.
\end{lemma}
\begin{proof}
Construct an auxiliary series $\{\tilde{\Delta}_i(n)\}$ as follows:
\begin{equation*}
\tilde{\Delta}_i(n) = \bar{\rho}_i \tilde{\Delta}_i(n+1) + Q_i,
\end{equation*}
where $n = N-1, \cdots, 0$, and $\tilde{\Delta}_i(N) = Q_{iN}$.
Using Lemma \ref{lemma_RDE}, it can be seen that $\tilde{\Delta}_i(n) + \Delta_i(n) \geqslant 0$.
On the other hand, we have
\begin{equation*}
\tilde{\Delta}_i(n) = \bar{\rho}^{N-n}_i Q_{iN} + \sum_{l=1}^{N-(n+1)}\bar{\rho}_i^l Q_i.
\end{equation*}
Thus, the result in Lemma \ref{lemma_delta_auxiliary} holds.
\end{proof}

\emph{Proof of Theorem \ref{col_sufficient_LTI}}: By direct calculation, we have
\begin{align*}
& P_i(1) - [A-BK_i + (\lambda_i - 1) B G_i]^{H} \nonumber \\
& \times P_i(1)[A-BK_i + (\lambda_i -1)B G_i]\nonumber\\
= & P_i(1) - \bar{A}_i^{\rm T} P_i(1) \bar{A}_i -(\lambda_i-1)^{\rm H} \Delta_i(1)^{\rm T}\nonumber \\
& \times B(R + B^{\rm T}P_i(1)B)^{-1} B^{\rm T} P_i(1)\bar{A}_i\nonumber\\
 & -(\lambda_i -1) \bar{A}_i^{\rm T}P_i(1)B(R + B^{\rm T}P_i(1)B)^{-1}B^{\rm T}\Delta_i(1)\nonumber\\
 & -\|\lambda_i -1\|^2 \Delta_i(1)^{\rm T} B (R + B^{\rm T}P_i(1)B)^{-1}\nonumber \\
 & \times B^{\rm T}P_i(1)B(R + B^{\rm T}P_i(1)B)^{-1} B^{\rm T} \Delta_i(1),
\end{align*}
where $G_i = (R+B^{\rm T}P_i(1)B)^{-1}B^{\rm T}\Delta_i(1)$ has been used.
According to Lemma 5, we further have
\begin{align*}
& P_i(1) - [A-BK_i + (\lambda_i - 1) B G_i]^{H} \nonumber \\
& \times P_i(1)[A-BK_i + (\lambda_i -1)B G_i]\nonumber\\
\geqslant & P_i(1) - \bar{A}_i^{\rm T} P_i(1) \bar{A}_i - \|\lambda_i -1\|^2 \Delta_i(1)^{\rm T}\nonumber \\
& \times (I + B(R+B^{\rm T}P_i(1)B)^{-1}B^{\rm T}) \Delta_i(1)- \Pi_i.
\end{align*}
Using Lemma \ref{lemma_special_G_i} with $\lambda_i = 1$, we get
\begin{align*}
& P_i(1) - [A-BK_i + (\lambda_i - 1) B G_i]^{H} \nonumber \\
& \times P_i(1)[A-BK_i + (\lambda_i -1)B G_i]\nonumber\\
> & Q_i + \|\lambda_i -1\|^2 \Delta_i(1)^{\rm T}\nonumber \\
& \times (I + B(R+B^{\rm T}P_i(1)B)^{-1}B^{\rm T}) \Delta_i(1)- \Pi_i.
\end{align*}
Finally, applying the result in Lemma \ref{lemma_delta_auxiliary} and using the condition in (\ref{equ_sufficient_Q}), we obtain that
$P_i(1) - [A-BK_i + (\lambda_i - 1) B G_i]^{H} P_i(1)[A-BK_i + (\lambda_i -1)B G_i]>0$.
That is, $A-BK_i + (\lambda_i - 1) B G_i$ is stable for all $\lambda_2,\cdots, \lambda_M$.
According to Theorem \ref{thm_iff}, the consensus can be reached. This completes the proof.
\subsection{Sufficient Conditions for One-dimensional Systems}
For each agent $i$ of one-dimensional linear dynamics, the system equation becomes
\begin{equation}\label{equ_one_dimension_system}
x_i(k+1) = a x_i(k) + b u_i (k).
\end{equation}
For one-dimensional systems, the corresponding parameters $R, Q_i, Q_{iN}, P_i(n), \Delta_i(n)$ reduce to scalars $r, q_i, q_i^N, p_i(n),\delta_i(n)$.
The result for ensuring consensus is reported in the following corollary.
\begin{corollary}\label{cor_consensus_1D}
For system in (\ref{equ_one_dimension_system}) with the network topology $\mathcal{G}$, assume that $r_i$ is designed as in (\ref{equ_design_R}) and the  $\mathcal{G}$ contains a panning tree.
If $q_i$, $q_i^N$ and $r$ are designed such that
\begin{align}
& p_i(N) - p_i(N-1) >0,\label{equ_qi_qiN}\\
& |\alpha_i|^{N-1} q_i^N + \sum_{l = 1}^{N-2}|\alpha_i|^l q_i < \bar{\theta}_{min},\label{equ_qn_bound}
\end{align}
then all the states of each agent can reach consensus. Here, $\alpha_i \triangleq \frac{r a}{r + b^2 p_i(1)}$,
$\bar{\theta}_{min} = \min_{i}\{\theta_i\}$, $\theta_i = |ar|\frac{\sqrt{(1-a_{ci}^2)b_i^2 + (1-a_i)^2 a_{ci}^2}-(|1-a_i|a_c^2)}{(1-a_i)^2a_{ci}^2 + b_i^2}$,
$a_{ci} = \frac{ar}{r + b^2 p_i(1)}$, $a_i = {\rm Re}(\lambda_i)$, $b_i = {\rm Imag}(\lambda_i)$, and $\lambda_i$ $i=2, \cdots, M$ are the eigenvalues of $\tilde{\mathcal{L}}$.
\end{corollary}
\begin{proof}
By plugging $K_i = \frac{ab p_i(1)}{r + b^2 p_i(1)}$ and $G_i = \frac{b\delta_i(1)}{r + b^2 p_i(1)}$ into $A-B K_i + (\lambda_i -1) B G_i$, we have
\begin{align*}
A-BK_i + (\lambda_i -1) B G_i  = \frac{ar + (1-\lambda_i)b^2 \delta_i(1)}{r + b^2 p_i(1)}.
\end{align*}
To achieve consensus, we need to develop conditions to ensure that $|\frac{ar + (1-\lambda_i)b^2 \delta_i(1)}{r + b^2 p_i(1)}|<1$ for $\lambda_2, \cdots, \lambda_M$. To that need, we consider the term $T\triangleq |a r + (1-\lambda_i)b^2 \delta_i(1)|^2-|r + b^2 p_i(1)|^2$.
Firstly, we derive an upper bound of $\delta_i(1)$. Define a sequence $\{\tilde{\delta}_i(n), n = N-1, \cdots, 0\}$ as
\begin{equation}\label{equ_tilde_delta}
\tilde{\delta}_i(n) = \frac{ar\tilde{\delta}_i(n+1)}{r + b^2 p_i(1)} + q_i,
\end{equation}
where $\tilde{\delta}_i(N) = q_{iN}$. Because of (\ref{equ_qi_qiN}), Lemma \ref{lemma_RDE} can be used, implying $p_i(1)< \cdots < p_i(N)$. As a result, $|\tilde{\delta}_i(n)| \geqslant |\delta_i(n)|$.
Therefore, a sufficient condition for guaranteeing $T<0$ is
\begin{align}\label{equ_1D_inequality}
(|ar| + |1-a_i| b^2 |\tilde{\delta}_i(1)|)^2 + b_i^2 b^2 |\tilde{\delta}_i(1)|^2 -(r + b^2 p_i(1))^2 < 0.
\end{align}
By some algebraic operations, (\ref{equ_1D_inequality}) reduces to
\begin{align}\label{equ_1D_inequality_second}
(|c_i|^2 + |d_i|^2) (\tilde{\delta}_i(1))^2 + 2 |a_c| |c_i| |\tilde{\delta}_i(1)| + |a_c|^2 - 1 <0,
\end{align}
where $c_i = \frac{|1-a_i|b^2 |a_c|}{ar}$ and $d_i = \frac{b^2 b_i}{ar}$.

On the other hand, from (\ref{equ_tilde_delta}), we can obtain that $|\tilde{\delta}_i(1)|\leqslant |\alpha_i|^{N-1} q_{iN} + \sum_{l = 1}^{N-2}|\alpha_i|^l q_i$.
Using the condition in (\ref{equ_qn_bound}), we have $|\tilde{\delta}_i(1)|\leqslant \bar{\theta}_{min}$, which ensures (\ref{equ_1D_inequality_second}) holds.
This completes the proof.
\end{proof}

\section{Simulation Studies}\label{Sec_simulation}
In this section, two examples are provided to verify the theoretical results.
\subsection{One-dimensional Case}
Consider a multi-agent system with $5$ agents, and the model for each agent is given as
\begin{equation*}
x_i(k+1) = 2 x_i(k) + u_i(k).
\end{equation*}
The adjacency matrix $\mathcal{A}$ of $\mathcal{G}$ is given as
$\mathcal{A} = \left[
   \begin{array}{ccccc}
     0 & 1 & 0 & 0 & 1 \\
     0 & 0 & 1 & 0 & 0 \\
     0 & 0 & 0 & 1 & 0 \\
     1 & 0 & 1 & 0 & 0 \\
     1 & 1 & 1 & 0 & 0 \\
   \end{array}
 \right]
$. The Laplacian matrix $\tilde{\mathcal{L}}$ of $\tilde{\mathcal{G}}$ can be figured out as $\tilde{\mathcal{L}} = \left[
   \begin{array}{ccccc}
     1 & -\frac{1}{2} & 0 & 0 & -\frac{1}{2} \\
     0 & 1 & -1 & 0 & 0 \\
     0 & 0 & 1 & -1 & 0 \\
     -\frac{1}{2} & 0 & -\frac{1}{2} & 1 & 0 \\
     -\frac{1}{3} & -\frac{1}{3}  & -\frac{1}{3}  & 0 & 1 \\
   \end{array}
 \right]$.
It can be seen that $\mathcal{G}$ contains a panning tree.
The parameters $q_i$, $q_{iN}$ are designed as $q_i=2$, and $q_{iN}=6$, $i=1,\cdots, 5$.
The parameter $r$ is designed as $r = 1$, and thus, the corresponding $r_i$, $i=1,\cdots, 5$,
are $r_1 = \frac{1}{2}$, $r_2 = 1$, $r_3 = 1$, $r_4 = \frac{1}{2}$, and $r_5 = \frac{1}{3}$.
The horizon is chosen as $N=3$.
By checking the condition in (\ref{equ_qi_qiN}), we have $p_i(3)-p_i(2) = 0.5714>0$.
Furthermore, $\bar{\theta}_{min}$ is calculated as $3.3391$,
and the term $|\alpha_i|^{2} q_{iN} + |\alpha_i| q_i = 1.2186$.
Thus, (\ref{equ_qn_bound}) verifies. According to Corollary \ref{cor_consensus_1D}, the multi-agent system will achieve consensus.
We plot the simulated trajectories of the five agents in Fig. \ref{fig_1d_state}, showing that the system can reach consensus.
\begin{figure}[!hbt] \centering
\includegraphics[width=0.5\textwidth]{1D_state.eps}
\caption{Trajectories for 5 agents with 1D system dynamics.}\label{fig_1d_state}
\end{figure}

\subsection{General Linear Systems Case}
Consider a multi-agent system with $3$ agents, and each of a general LTI dynamics.
The system matrices are $A = \left[
                               \begin{array}{cc}
                                 2 & 0 \\
                                 1.2 & -1 \\
                               \end{array}
                             \right]$,
$B = \left[\begin{array}{c}
1 \\
1 \\
\end{array}
\right]$.
The diagraph $\mathcal{G}$ contains a spanning tree, and it adjacency matrix $\mathcal{A}$ is $\mathcal{A} = \left[
                                                                        \begin{array}{ccc}
                                                                          0 & 1 & 1 \\
                                                                          0 & 0 & 1 \\
                                                                          1 & 1 & 0 \\
                                                                        \end{array}
                                                                      \right]$.
Thus, the corresponding matrix $\tilde{\mathcal{L}} = \left[
                                                      \begin{array}{ccc}
                                                        1 & -\frac{1}{2} & -\frac{1}{2} \\
                                                        0 & 1 & -1 \\
                                                        -\frac{1}{2} & -\frac{1}{2} & 1 \\
                                                      \end{array}
                                                    \right]
$.
The matrices $Q_i$ and $Q_{iN}$ are designed as $Q_i = {\rm \diag}(2, 2)$ and $Q_{iN} = {\rm \diag}(15, 20)$, $i=1, 2, 3$.
The matrices $R_i$ are designed as $R_1 = \frac{1}{2}$, $R_2 = 1$ and $R_3 = \frac{1}{2}$, respectively, which satisfies (\ref{equ_design_R}) with $R = 1$. The prediction horizon is chosen as $N = 10$.

Calculate $P_i(10) - P_i(9) = \left[
                                \begin{array}{cc}
                                  5.2  & -6 \\
                                  -6 & 9.111 \\
                                \end{array}
                              \right]>0
$. Thus, the condition in (\ref{equ_monotically_P}) is verified.
The eigenvalues of $\tilde{\mathcal{L}}$ are $\lambda_1 = 0$, $\lambda_2 = 1.5 + j0.5$, and $\lambda_3 = 1.5 - j0.5$.
When $\lambda_2 = 1.5 \pm j0.5$, the left-hand side of (\ref{equ_sufficient_Q}) is $[0.7045 -0.0621; -0.0621 0.7089]$, which is positive definite.
Therefore, the condition in (\ref{equ_sufficient_Q}) is satisfied.
The simulated system trajectories are plotted in Fig. \ref{fig_2d_state1} and Fig. \ref{fig_2d_state2}, respectively.
From these two figures, it can be seen that the
consensus is reached.

\begin{figure}[!hbt] \centering
\includegraphics[width=0.5\textwidth]{2D_state1.eps}
\caption{Trajectories of state 1.}\label{fig_2d_state1}
\end{figure}
\begin{figure}[!hbt] \centering
\includegraphics[width=0.5\textwidth]{2D_state2.eps}
\caption{Trajectories of state 2.}\label{fig_2d_state2}
\end{figure}

\section{CONCLUSIONS}\label{Sec_Conclusion}
In this paper, we have proposed a novel consensus scheme by using the distributed RHC for general LTI multi-agent systems.
The necessary and sufficient conditions for ensuring consensus have been developed.
Furthermore, we have developed more easily solvable conditions for multi-agent systems of general LTI and one-dimensional system dynamics, respectively. The developed theoretical results have been verified by two numerical studies.

\bibliographystyle{IEEEtran}
\bibliography{ref}

\end{document}

config: arxiv


TITLE: How to show that in ABCD, if (AB) isn’t parallel to (CD), then the line joining the middle points of AD and BC is concurrent to (AB) and (CD)?
QUESTION [1 upvotes]: I have to show that in a non complex quadrilateral ABCD if (II’) is
the line joining the middle points I and I’ of AD and CD then the lines (AB), (CD) and (II’) are either parallel or concurrent.
For the parallel case it is pretty easy using the bimedian of a trapezoid, but for the concurrent case I can’t seem to find much and even my professor isn’t able to solve the exercise, he said that he forgot to add the condition that (AD)//(BC) but in this case it is almost trivial and with all examples I have drawn it does work even without this condition.

REPLY [0 votes]: Counter Example

The image clearly shows that the 3 lines are not concurrent


TITLE: Probability of mixed type question
QUESTION [0 upvotes]: Let X be a random variable of the mixed typed having the CDF
$F(x)=\begin{cases} 0, \text{x< -1} \\ \frac{x+2}{3}, \text -1 \leq x<1 \\ 1, \text 1 \leq x \end{cases}$
Find the indicated probabilities
$a). P(X<0)=0$
$b). P(x<-1)=0$
$c).P(X \leq -1)=1$
$d). P(-1 \leq x < \frac{1}{2})= P(\frac{1}{2})-P(-1)$= $\frac{5}{6}-\frac{1}{3}$
$e). P(-1<X<1)$= $\frac{2}{3}$
Are these correct?

REPLY [1 votes]: a) and d) are wrong. the others are correct/.
a) $P(X<0)=\frac  1 3 +\int_{-1}^{0} \frac 1 3 dx=\frac 2 3$.
 For d) add $\int_0^{1/2} \frac 1 3 dx$ to $\frac 2 3$.


TITLE: Prove $n^{\ln(n)} < n!$ for $n$ big enough
QUESTION [3 upvotes]: I want to prove $n^{\ln(n)} < n!$ for $n$ big enough, but right now all my attempts failed...
I tried mathematical induction, but that's not working, I get stuck at showing:
$$(n + 1) \cdot n^{\ln(n)} \geq (n+1)^{\ln(n+1)}$$
I thought about trying to show $\ln(n)^2 < \ln(n!) = \sum_{k=1}^n\ln(n)$ but that also got me nowhere...
Any hint would be appreciated!

REPLY [1 votes]: Pick some $N$ such that for all $n >N$ we have:
$$\frac{n}{2} \geq \sqrt{n}$$
and
$$\frac{n}{4}-\frac{1}{2} \geq \log(n)$$
Then
$$n! \geq (\lfloor \frac{n}{2} \rfloor+1)(\lfloor\frac{n}{2}\rfloor+2)...n \\\geq \left( \frac{n}{2} \right)^{\frac{n}{2}-1} \geq \left( \sqrt{n} \right)^{\frac{n}{2}-1} = n^{{\frac{n}{4}-\frac{1}{2}}} \geq n^{\log(n)} $$


TITLE: $\int f_kd\mu_k\to\int fd\mu$?
QUESTION [4 upvotes]: If a measure $\mu_k$ converges weakly to a measure $\mu$, i.e. $\int fd\mu_k\to \int fd\mu$ for every $f\in C_b(\mathbb{R})$ (contiuous and bounded functions), and let $f_k\to f$ a.e. pointwise. Then I was wondering what extra condition we need so that $\int f_kd\mu_k\to\int fd\mu$. I have $$\int f_kd\mu_k=\underbrace{\int fd\mu_k}_{\to\int fd\mu}+\int (f_k-f)d\mu_k$$ but I am not sure when the second term goes to zero.

REPLY [3 votes]: Some equicontinuity property along with uniform integrability is enough. Here is a result by Mann, Wald, Prokhorov, Rubin (see, Kallenberg, O. Foundations of probability, second ed. Springer. 2001, pp. 76)

Suppose  $(S,d)$ and $(T,\rho)$ are  metric spaces, $\{X_n,X:n\in\mathbb{N}\}$ are random variables taking values in $S$ such that  $X_n\stackrel{law}{=}\mu_n\stackrel{n}{\Longrightarrow}\mu\stackrel{law}{=} X$. If $(f_n,f:n\in\mathbb{N})$ are measurable functions from $S$ into  $T$, and there is a measurable set $C\subset S$ such that

$\operatorname{supp}\mu\subset C$, and
$f_n(s_n)\xrightarrow{n\rightarrow\infty}f(s)$ for any $s_n\rightarrow s\in C$,
Then $f_n(X_n)\stackrel{n}{\Longrightarrow} f(X)$, that is $$\int g(f_n(X_n))dP=\int_S g(f_n(x))\,\mu_n(dx)\xrightarrow{n\rightarrow\infty}\int_S g(f(x))\,\mu(dx)=\int g(f(X))\,dP$$  for all $g\in\mathcal{C}_b(T)$.

If $T=\mathbb{R}$, and the sequence $(f_n(X_n):n\in\mathbb{N})$ is uniformly integrable, then you may use $g(t)=t$ to get the convergence you are looking for, that is $$\int f(x)\,\mu_n(dx)\xrightarrow{n\rightarrow\infty}\int f(x)\,\mu(dx)$$
(See Billingsley, Convergence of Probability measures, Wiley 1968, Theorem 5.4)

A slightly more general version of the result above can be found in van der Vaart, A.W. Asymptotic statistics, Cambridge 1998, pp. 258-259 where some measurability assumptions are dropped and the integrals are "upper" integrals (upper Daniell integrals).
In both references, the proof of the statements relay on the Portmanteau theorem.


TITLE: How should I solve this kind of problem of Arithmetic progression?
QUESTION [0 upvotes]: $x^{n-1} - 2x^{n-2} +3x^{n-3} - 4x^{n-4}  ------------ ± n $ where $n\xrightarrow\ \infty$ and $1>x>-1$

my attempt

in the following a normal term at r position from right is in the
  form of the following.
      $$T_r= (-1)^{r-1}rx^{n-r} $$
      then two solutions should be there one is where n is odd then sum is $$\sum_{n=0}^{\infty} T_n$$ where $T_r$ is negative
and another is where n is even then $$\sum_{n=0}^{\infty} T_n$$ where $T_r$ is positive

what should I do next?

REPLY [0 votes]: Let the sum be $S(x)$ and compute $xS(x)+S(x)$. What you get after simplification is
$$x^n-x^{n-1}+x^{n-2}-\cdots\mp x\pm n.$$
The sum of the alternating geometric series is
$$-\frac{x+(-x)^{n+1}}{x+1},$$ which is finite. Then the sum diverges.


TITLE: Integral = 0 implies function = 0?
QUESTION [3 upvotes]: If $f : \mathbb{R}^2 \to \mathbb{R}$ is continuous and such that
$$
\int_{-\infty}^{\infty}\int_{-\infty}^{\infty} \! f(x,t) \phi(x,t) \, \mathrm{d}x \, \mathrm{d}t = 0
$$
for all $\phi \in C_c^{\infty}(\mathbb{R}^2)$ (that is, for all compactly supported smooth functions), then is it true that $f$ must be identically equal to $0$ ?
I thought taking, in particular, $\phi_n \in C_c^{\infty}(\mathbb{R}^2)$ to be equal to $0$ outside the disk of radius $n$ centered at the origin, to $f$ where $f \geq 0$ and to $-f$ where $f < 0$ would permit us to prove this, but unfortunately it seems like such $\phi_n$ need not be $C^{\infty}$...

REPLY [2 votes]: We can assume that $f$ has compact support. If not, take a $C_c^\infty$ partition of unity $\{\psi_n\}$ and show that $\psi_n(x)f(x)=0$ as below. Then $f=\sum\limits_n\psi_n(x)f(x)=0$.
Given an $\epsilon\gt0$, we can find a $\phi\in C_c^\infty$ so that
$$
\int_{-\infty}^\infty\int_{-\infty}^\infty|f(x,t)-\phi(x,t)|^2\,\mathrm{d}x\,\mathrm{d}t\le\epsilon
$$
The hypothesis then implies
$$
\begin{align}
&\int_{-\infty}^\infty\int_{-\infty}^\infty|f(x,t)|^2\,\mathrm{d}x\,\mathrm{d}t\\
&\le\int_{-\infty}^\infty\int_{-\infty}^\infty|f(x,t)|^2+|\phi(x,t)|^2\,\mathrm{d}x\,\mathrm{d}t\\
&=\int_{-\infty}^\infty\int_{-\infty}^\infty|f(x,t)-\phi(x,t)|^2\,\mathrm{d}x\,\mathrm{d}t\\[6pt]
&\le\epsilon
\end{align}
$$
Since $\epsilon$ is arbitrary, we have
$$
\int_{-\infty}^\infty\int_{-\infty}^\infty|f(x,t)|^2\,\mathrm{d}x\,\mathrm{d}t=0
$$


TITLE: Antiderivative and elementary functions
QUESTION [2 upvotes]: Is there a theorem or method to prove that we can't express the antiderivative of some functions with elementary functions ? For example Gamma or Zeta or $\dfrac{\sin x}{x!}$? thanks

REPLY [1 votes]: Yes, Liouville's theorem.
The use of such a result in order to prove the non-existence of an elementary primitive for some functions (among them, the famous $e^{-x^2}$) is explained in these notes by Brian Conrad.


TITLE: Normalization of a four-velocity when constructing the metric from the EM tensor
QUESTION [1 upvotes]: I've been following the MIT General Relativity Course. In lecture (14) the concept of linearized gravity is introduced. This is then demonstrated by showing how we can recieve the Newtonian limit from such a approach.
We assume we have the metric that can be locally written as
$$
g_{\mu \nu} = \eta_{\mu \nu} + h_{\mu \nu}
$$
where $\eta$ is the Minkowski metric and $h$ is a correction, we work only in the order $O(h^2)$.
Using the correct gauge we recieve the equations
$$
\Box \bar{h}_{\alpha\beta} = -16 \pi G \ T_{\alpha\beta}.
$$
where $\bar{h}$ is the trace free part of $h$, i.e. $\bar{h}_{\alpha\beta}= h_{\alpha\beta}- \frac{1}{2}\eta_{\alpha\beta}h$.
Now the lecturer then says, if consider static non-relativistic perfect fluid solution, we have that $$T_{\mu \nu} = \rho u_\mu u_\nu, $$ since this is static the pertubation $h$ must be indepedent of the time parameter, we neglect the preassure part of $T$.
Now presumably if we consider the observer $u_\mu = \{1,0,0,0\}$ we get
$$
T_{00} = \rho
$$
and all other terms zero, we then get the metric
$$
ds^2 = -(1+ 2 \Phi) dt^2 + (1- 2 \Phi) (dx^2 + dy^2 + dz^2),
$$
with $\Phi$ being the Newtonian potential.
But I am really not convinced by this. How can we tell that a four-velocity is $u_\mu = \{1,0,0,0\}$? Such a four velocity is surely not normalized under the metric we receive later and thus should hold no physical meaning.

REPLY [0 votes]: You are considering only weak fields, thus any corrections to $T_{00}=\rho$ due to normalization will be even weaker and will not be kept in the metric within linear approximation.
You can see this directly by adding normalization $u_\mu=(A,0,0,0)$, which will lead to the metric
$$
ds^2 = -(1+ 2 A^2\Phi) dt^2 + (1- 2 A^2\Phi) (dx^2 + dy^2 + dz^2),
$$
From which you will get
$$A^2=\frac{1}{4\Phi}\left[\sqrt{1+8\Phi}-1\right]=1-\Phi+o(\Phi^2)$$


TITLE: Proving the convergence of $\sum_{n=1}^{\infty}\frac{n^n}{e^n (n+1)!}$
QUESTION [3 upvotes]: I'm tasked with the simple problem of finding the interval of convergence of
$$\sum_{n=1}^{\infty}\frac{x^n n^n}{(n+1)!}.$$
Using the ratio test, I've found that it certainly converges on $|x|<\frac{1}{e}$; however, I haven't been able to test the endpoints of that interval. (It's too much work to put all the $\LaTeX$ here.) When $x=\frac{1}{e}$, the series becomes
$$\sum_{n=1}^{\infty}\frac{n^n}{e^n (n+1)!},$$
which WolframAlpha claims converges by the comparison test. But I can't find another series to compare with even after careful thinking. Would someone be able to give me a hint in the right direction? Thanks!

REPLY [1 votes]: We have
$$
\frac{{n^n }}{{e^n (n + 1)!}}\frac{{e^{n + 1} (n + 2)!}}{{(n + 1)^{n + 1} }} = \frac{e}{{\left( {1 + \frac{1}{n}} \right)^n }}\frac{{n + 2}}{{n + 1}}.
$$
By Maclaurin series expansion
\begin{align*}
\left( {1 + \frac{1}{n}} \right)^{ - n}  = \exp \left( { - n\log \left( {1 + \frac{1}{n}} \right)} \right) &= \exp \left( { - 1 + \frac{1}{{2n}} + \mathcal{O}\!\left( {\frac{1}{{n^2 }}} \right)} \right) \\ & = \frac{1}{e}\left( {1 + \frac{1}{{2n}} + \mathcal{O}\!\left( {\frac{1}{{n^2 }}} \right)} \right)
\end{align*}
and
$$
\frac{{n + 2}}{{n + 1}} = \frac{{1 + 2/n}}{{1 + 1/n}} = 1 + \frac{1}{n} + \mathcal{O}\!\left( {\frac{1}{{n^2 }}} \right).
$$
Consequently
$$
\frac{{n^n }}{{e^n (n + 1)!}}\frac{{e^{n + 1} (n + 2)!}}{{(n + 1)^{n + 1} }} = 1 + \frac{3}{{2n}} + \mathcal{O}\!\left( {\frac{1}{{n^2 }}} \right).
$$
Hence,
$$
\lim_{n\to+\infty} n\!\left( {\frac{{n^n }}{{e^n (n + 1)!}}\frac{{e^{n + 1} (n + 2)!}}{{(n + 1)^{n + 1} }} - 1} \right) = \frac{3}{2} > 1,
$$
and so the series converges by Raabe's test.


TITLE: How to locate a coordinate on a squircle?
QUESTION [1 upvotes]: I am solving a finite difference problem with a squircle as the boundary. I want to know how to locate a point on the squircle with equation $x^4 + y^4 = 1$. It has the centre $(0,0)$ and radius $1$.
I know for a circle any line from the centre to a point on the circle is the radius so to locate say, the x-coordinate of a point I would use Pythagoras theorem. How do I locate say, an $x$-coordinate of a point on a squircle?

REPLY [1 votes]: If you know $y$ then
$$
x = (1 - y^4)^{1/4} .
$$
If you know the angle $\theta$ of the "radius" $r$ then
$$
x = r \cos \theta
$$
where  $r$ is given by
$$
r  = \left(\frac{1}{\cos^4\theta + \sin^4\theta}\right)^{1/4}.
$$


TITLE: discrete-time to continuous-time state space
QUESTION [0 upvotes]: What are the formulas to convert discrete-time state space ($A_d,B_d,C_d,D_d$) to continuous-time state space ($A,B,C,D$)?
i.e.,
Convert the state space
$x_{k+1} = A_d x_{k} + B_d u_k$
$y_k = C_d x_{k} + D_d u_k$
To
$\dot{x}(t) = A x(t) + B u(t)$
$y(t) = C x(t) + D u(t)$
x: state vector
y: output vector
u: input (or control) vector

REPLY [2 votes]: One can try to do the inverse of zero order hold discretization:
\begin{align}
\begin{bmatrix}A_d & B_d \\ 0 & I\end{bmatrix} &= e^{\begin{bmatrix}A & B \\ 0 & 0\end{bmatrix} T}, \tag{1a} \\
C_d &= C, \tag{1b} \\
D_d &= D. \tag{1c}
\end{align}
So one has to take the matrix logarithm of the matrix containing $A_d$ and $B_d$ from $(1a)$. However, this is not always well defined, especially in the context of state space models of physical systems where $A$ and $B$ should only contain finite real values. For example if $A_d$ has one eigenvalue at some negative real value then $A$ should have one eigenvalue which has only a nonzero imaginary part and not an associated complex conjugate eigenvalue. Another example would be if $A_d$ has eigenvalues at zero, since the logarithm of zero is not well defined. However, one could also interpret those eigenvalues as a delay. Furthermore, a matrix logarithm it not unique since $e^{M+2\,\pi\,i\,k\,I}=e^{M},\ \forall\,k\in\mathbb{Z}$. However, one could add the assumption that the imaginary parts of the eigenvalues of $A$ have the smallest possible absolute value (which can also be interpret as to saying that the discrete system is not "aliasing" the dynamics of the continuous system).
Another popular discretization method is the bilinear transform, a.k.a. the Tustin's method, which I believe gives a better behaved back and forth mapping between the continuous and discrete time representation. Namely, for discrete to continuous one can use the following relation
$$
z = \frac{2 + s\,T}{2 - s\,T}. \tag{2}
$$
Substituting $(2)$ in
$$
z\,x = A_d\,x + B_d\,u, \tag{3}
$$
and factoring out $s$ yields
$$
s \left((A_d + I)\,x + B\,u\right) = \frac{2}{T} \left((A_d - I)\,x + B\,u\right). \tag{4}
$$
Now by defining a new state vector as $x' = (A_d + I)\,x + B\,u$ and solving it for $x$ yields
$$
x = (A_d + I)^{-1} (x' - B\,u). \tag{5}
$$
Substituting $(5)$ in $(4)$ and $y = C_d\,x + D_d\,u$ yields
\begin{align}
s\,x' &= A\,x' + B\,u, \tag{6a} \\
y &= C\,x' + D\,u, \tag{6b}
\end{align}
with
\begin{align}
A &= \frac{2}{T} (A_d - I)\,(A_d + I)^{-1}, \tag{7a} \\
B &= \frac{2}{T} \left(I - (A_d - I)\,(A_d + I)^{-1}\right) B_d, \tag{7b} \\
C &= C_d\,(A_d + I)^{-1}, \tag{7c} \\
D &= D_d - C_d\,(A_d + I)^{-1} B_d, \tag{7d} \\
\end{align}
which should always allow one to define a mapping from discrete to continuous if minus one is not an eigenvalue of $A_d$.


TITLE: Total probability question.
QUESTION [1 upvotes]: Tennis player at Monday had $4$ used and $5$ unused tennis balls. Then, on Tuesday, he randomly picked and used three of them. On Wednesday, he picked one used and one unused ball. What is the probability that he picked two used balls on Thursday?
Here are all of the events:
$B$ player picked two used balls on Thursday
$H_1$ player picked three used balls on Monday
$H_2$ player picked three unused balls on Monday
$H_3$ player picked two used balls and one unused on Monday
$H_4$ player picked two unused balls and one used on Monday
This alone would require total probability formula:
$$P(B)=P(H_1)P(B|H_1)+P(H_2)P(B|H_2)+P(H_3)P(B|H_3)$$
However, that Wednesday makes a mess here so obviously, I cannot use this formula at least not this way. Any suggestion appreciated!

REPLY [2 votes]: Let $T$ denotes the number of unused balls used on Tuesday.
$$P(T=0)=\frac{4}{9}\cdot\frac{3}{8}\cdot\frac{2}{7}=\frac{24}{504}\\
P(T=1)=\binom31\cdot\frac{4}{9}\cdot\frac{3}{8}\cdot\frac{5}{7}=\frac{180}{504}\\
P(T=2)=\binom32\cdot\frac{4}{9}\cdot\frac{5}{8}\cdot\frac{4}{7}=\frac{240}{504}\\
P(T=3)=\frac{5}{9}\cdot\frac{4}{8}\cdot\frac{3}{7}=\frac{60}{504}\\$$
The number of used balls by Tuesday is $4+T$.
The number of used balls by Wednesday is $4+T+1=5+T$.
The probability of getting two used balls is
$$p=\sum_{0\le t\le3}\binom{3}{2}\frac{(5+T)(4+T)(4-T)}{9\cdot8\cdot7}P(T=t)$$
which can be easily calculated.


TITLE: Does Newton's 3rd Law apply to friction?
QUESTION [0 upvotes]: Supposed body A slides on a surface. The will be a kinetic friction that acts on body A and opposite its relative motion.
However, is there a kinetic friction that acts on the surface too i.e. the direction is opposite to the kinetic friction that acts on body A?

REPLY [1 votes]: Of course, Newton's laws are valid on all forces provided that an inertial frame is considered (can apply in non inertial frames too, but let's not discuss that now as it is irrelevant). So okay, if you want to apply 3rd law on friction, there will be an equal and opposite force on the surface too. The best way to see this is a two-block problem where you place a block on another one. Now, the floor on which the lower block is kept shouldn't be too rough, a moderately rough surface will do. Now provide the upper block a velocity relative to the lower one. You will see that both blocks will move seperately initially and gradually they will start moving together afterwards. You may also choose to calculate the time at which they start moving together, provided you know the coefficient of friction and other details as may be required, but since that's not exactly the question here, I'll leave it for now.
Diagram Reference
Use this link if you want a diagram reference for the situation I have described. Try applying Newton's second law and kinematics' relations to find the time at which start moving together and other parameters.
I hope this answers your question!


TITLE: Evaluation of $\sum_{n\geq1}\frac{1}{n}\ln(1+\frac{1}{n})$
QUESTION [5 upvotes]: Coming across the calculation of a special integral I get stuck on the following series, which I have given its integral representation :
$$\text{J}=\sum_{n\geq1}\frac{1}{n}\ln\bigg(1+\frac{1}{n}\bigg)=\int_{0}^{1}\frac{1}{x}\bigg(\psi(1+x)+\gamma \bigg)dx\,$$
Where $\psi$ denotes the digamma function and $\gamma$ represents the Euler-Mascheroni constant. I am wondering if such a series has a closed-form.

REPLY [1 votes]: I deleted my comment, since I found a better approximation. By the use of Binet's formula (see Binet), one can derive $${\rm J}=\sum_{k=2}^\infty \frac{(-1)^k}{k-1} \, \zeta(k)$$ which converges somewhat slowly. By partial summation this can be brought to $$\zeta(2) \log 2 + \sum_{k=2}^\infty \frac{(-1)^k}{2} \left[\Psi\left(\frac{k+1}{2}\right) - \Psi\left(\frac{k}{2}\right)\right] \left[\zeta(k)-\zeta(k+1)\right] \, .$$ Another partial summation yields $$\zeta(2)\log 2 + \frac{1}{2} \sum_{n=1}^\infty \Big\{ \Psi(n+1) \left[\zeta(2n+2)-\zeta(2n+1)\right] \\
- \Psi(n+1/2) \left[\zeta(2n+2)-\zeta(2n)\right] + \Psi(n) \left[\zeta(2n+1)-\zeta(2n)\right] \Big\}$$ which converges a lot faster with exponential order ${\cal O}\left(\frac{1}{n4^{n+2}}\right)$. Cutting the series after only 5 terms yields \begin{align}{\rm J}&\approx 1.257743 \tag{approximation} \\ {\rm J} &= 1.257746... \tag{exact}\end{align} correct up to 6 digits.
Interestingly the number is somewhat similar to the alike looking sum
$$\gamma=\sum_{k=2}^\infty \frac{(-1)^k}{k} \, \zeta(k)$$
from which an alternative expression arises $${\rm J} = \gamma + \sum_{k=2}^\infty \frac{(-1)^k \, \zeta(k)}{k(k-1)} \, .$$


TITLE: Find parameters such that cumulative geometric distribution function equals cumulative exponential distribution function
QUESTION [0 upvotes]: I'm given three random variables $X,Y,Z$ with the following distributions: $X$~$Exp(\lambda)$ (exponential distribution), $Y$~$Geom(p)$ (geometric distribution), $Z$~$Y + a, a \in \mathbb{R}$. How can I find $a, p$ depending on $\lambda$ such that $\forall k \in \mathbb{N}_{\geq 0}$ the cumulative exponential distribution function $F^X(k)$ equals $F^Z(k)$?
How I tried to solve the problem:
$X$~$Exp(\lambda) \Rightarrow F^X(k) = \begin{cases}
0, k \leq 0\\
1 - e^{-\lambda k}, k > 0\\
\end{cases}$
$Y$~$Geom(p) \Rightarrow F^Y(k) = \sum_{i = 0}^{k}P(Y = i) = \sum_{i = 0}^{k} p(1 - p)^i = p\frac{1 - (1 - p)^{k + 1}}{1 - (1 - p)} = 1 - (1 - p)^{k + 1}$.
My guess now is that $Z$ is geometrically distributed as well. If I denote $k' := k + a$, then $P(Z = k') = p(1 - p)^{k + a}$. The cumulated geometric function then becomes:
$ F^Z(k) = \sum_{i = 0}^{k}P(Z = i) = \sum_{i = 0}^{k} p(1 - p)^{i + a} = p(1 - p)^{a}\frac{1 - (1 - p)^{k + 1}}{1 - (1 - p)} = (1 - p)^{a}(1 - (1 - p)^{k + 1})$.
This now brings me nowhere, because I could write $a:= 0\cdot \lambda$ but I cannot find anything for $p$. How can I the approach this problem? Or what am I doing here wrong?
Any suggestions are highly appreciated!

REPLY [0 votes]: The set of values of $Z$ are $\left\{a + k : k\ge 0\right\}$. You are looking for $p$ and $a$ such that for every $k\ge 0$ \begin{align}
F^{X}\left(a+k\right) &= F^{Z}(a+k)
\end{align}
this is equivalent to have \begin{align}
F^X(a+k) &= F^Y(k)\\
\Leftrightarrow \quad 1 - e^{-\lambda (a + k)} &= 1  - (1-p)^{k}\\
\Leftrightarrow \quad e^{-\lambda k}e^{-\lambda a} &= (1-p)^{k}\\
\end{align}
So $e^{-\lambda a} = 1$ and $e^{-\lambda} = 1-p$. Which implies $a = 0$ and $p = 1-e^{-\lambda}$.


TITLE: First Order Logic - Consequence and Interpretation
QUESTION [1 upvotes]: I'm trying to understand why this is false: $\varphi \vee \psi \models \chi \text{ iff } \varphi \models \chi \text{ or } \psi \models \chi.$
I think that the problem is that it can have two groups of interpretation and some doesn't hold for both. Any interpretation that shows why this is false will be very good accepted too. Thank you.

REPLY [1 votes]: Do you see why this is true: $\varphi\vee\psi\models\chi$ iff $\varphi\models\chi$ and $\varphi\models\chi$?
Combined with what you thought should be true, we would have:
$\varphi\models\chi$ and $\varphi\models\chi$ iff $\varphi\models\chi$ or $\varphi\models\chi$. Do you think that should be true?
Suppose $\chi$ happens to be the same as $\varphi$. Do you think this is true:
$\varphi\vee\psi\models\varphi$ iff $\varphi\models\varphi$ or $\psi\models\varphi$?