TITLE: outer measure and determining measurable sets
QUESTION [1 upvotes]: Define $\mu^*(E)$ as the number of points in $E$ if $E$ is finite and $\mu^*(E)= \infty$ if $E$ is infinite. Show that $\mu^*$ is an outer measure and determine the measurable sets.
Please give me a hint about this problem, specially the part that says "determine the measurable sets".

REPLY [2 votes]: Let's assume that $\mu^{\star}$ is indeed an outer measure.
Set $E$ is by definition $\mu^{\star}$-measurable if for each set $A\subseteq\Omega$: $$\mu^{\star}A\geq\mu^{\star}\left(A\cap E\right)+\mu^{\star}\left(A\cap E^{c}\right)\tag1$$
This is evidently true for each infinite $A$ (then $\mu^{\star}A=\infty$).
If $A$ is finite then also $A\cap E$ and $A\cap E^{c}$ are finite.
Finite sets are sent to their cardinality so again (1) is evidently
true.
So we conclude that every set $E$ is $\mu^{\star}$-measurable.

REPLY [1 votes]: Hint: Let $E\subseteq \mathbb{R}$. If $A\subseteq \mathbb{R}$ is infinite, can both $A\cap E$ and $A\cap E^c$ be finite? And what can you say about $A\cap E$ and $A\cap E^c$ when $A$ is finite?


TITLE: Question about continuity of a polynomial curve (Spline)
QUESTION [1 upvotes]: I'm getting a little bit confused trying to write my own algorithm for calculating a Spline.
Let's start saying that for my application I need that the curve, interpolating between more points, must be $C^{0}, C^{1}, C^{2}$ continuous and that the curve is given in the following parametric form.
$$
s_{i}(t) = a_{i} + b_{i}t + c_{i}t^{2} + d_{i}t^{3}
$$
where $t \in [0;1($
Now: according to this page and this paper (page: 129) the first derivative of the spline should be:
$$
s_{i}'(t) = b_{i} + 2c_{i}t + 3d_{i}t^{2}
$$
but I found in internet this tutorial (page 9) which is saying that not the derivative of $t$ must be calculated:

because we are interested in derivative with respect to $x,y,z$ or whatelse and $t$ is just a parametrization of the curve, so the latter should be not taken into consideration.
This sounds to be right to me. But since I ve to write an algorithm, I really have no idea on how to go further.
Which of the one is right?

REPLY [1 votes]: I assume the spline you're trying to construct will be $y$ as a function of $x$, as in the notes you cited, and not a parametric spline where $x$ and $y$ are functions of some parameter $t$.
On each interval $[x_i, x_{i+1}]$, you can define a "local" parameter $t$ to simplify the algebra, where $t = (x-x_i)/(x_{i+1}-x_i)$. Then you can write the equation of the cubic segment as $s_{i}(t) = a_{i} + b_{i}t + c_{i}t^{2} + d_{i}t^{3}$, where $t \in [0,1]$.
The conditions to enforce continuity say that certain derivatives at the far end of one segment ought to be equal to certain derivatives at the start of the next segment. But the derivatives involved are derivatives with respect to $\mathbf{x}$. Your formula $s_{i}'(t) = b_{i} + 2c_{i}t + 3d_{i}t^{2}$ gives a derivative with respect to $t$. Written more carefully, it says that
$$
\frac{ds_i}{dt}(t) = b_{i} + 2c_{i}t + 3d_{i}t^{2}
$$
and so
$$
\frac{ds_i}{dx}(x) = \frac{ds_i}{dt}(x) \frac{dt}{dx} =
\frac{b_{i} + 2c_{i}t + 3d_{i}t^{2}}{x_{i+1}-x_i}
$$
Then, the condition for $C_1$ continuity (for example) at $x = x_i$ is
$$
\frac{ds_{i-1}}{dx}(x=x_i) = \frac{ds_{i}}{dx}(x=x_i)
$$.
So, in short, the notes you cited are correct.


TITLE: Finding the sum of the reciprocals of the positive divisors of a number
QUESTION [2 upvotes]: Let $d_1, d_2, \dots , d_k$ be all the positive factors of a positive integer $n$  including $1$ and $n$. If $d_1+d_2+ \dots+d_k=72$, then find the value of $\frac{1}{d_1}+\frac{1}{d_2}+\dots+\frac{1}{d_k}$.

My attempt:
Let $a=p_1^{m_1}p_2^{m_2}\dots p_k^{m_k}$ be the prime factorization of $a$.
To calculate the sum of divisors function, $\sigma(a)$ we use the expression :
$(1+p_1+p_1^2+\dots+p_1^{m_1})(1+p_2+p_2^2+\dots+p_2^{m_2})\dots(1+p_k+p_k^2+\dots+p_k^{m_k})$
, which represents the sum of all possible positive factors of $a$ and is equal to:
$(\frac{p_1^{m_1+1}-1}{p_1-1})(\frac{p_2^{m_2+1}-1}{p_2-1})\dots(\frac{p_k^{m_k+1}-1}{p_k-1})$.
Now, if we replace each term in the each factor of the expression above the above expression by its reciprocal we shall obtain the sum of the reciprocals of all possible positive factors of $a$. This expression will be equal to:
$(1+1/p_1+1/p_1^2+\dots+1/p_1^{m_1})(1+1/p_2+1/p_2^2+\dots+1/p_2^{m_2})\dots(1+1/p_k+1/p_k^2+\dots+1/p_k^{m_k})$
which is equal to:
$(\frac{1-1/p_1^{m_1+1}}{1-1/p_1})(\frac{1-1/p_2^{m_2+1}}{1-1/p_2})\dots(\frac{1-1/p_k^{m_k+1}}{1-1/p_k})$ . This on simplication yields $\frac{\sigma(a)}{n}$.
Therefore for the information given in the question, the required value is $\frac{72}{n}$.
Is my reasoning and my answer correct? What are other methods to solve this question.

REPLY [3 votes]: Your answer is correct, but there's a much simpler way as the comments show.
The key idea is that if $\{d_1,\ldots,d_k\}$ is the set of divisors of  $n$ then $\{\frac n{d_1},\ldots,\frac n{d_k}\} = \{d_1,\ldots,d_k\}$ is also exactly the set of divisors of $n$, simply because each element of the first set is a divisor, and there is a bijection $d_k \to \frac n{d_k}$ for each $k$, so the number of elements in both sets are the same, so the first set covers all the divisors.
With this in mind, the sum of all elements of both sets are the same, hence we have :
$$
d_1+\ldots+d_k = \frac{n}{d_1}+ \ldots + \frac n{d_k}
\implies 72 = n\left(\frac 1{d_1}+ \ldots + \frac 1{d_k}\right)
$$
which gives the result. Your proof required the full expression of the $\sigma$ function, which we did not use.


TITLE: Problem with Singular Value Decomposition
QUESTION [2 upvotes]: I have a very trivial SVD Example, but I'm not sure what's going wrong.
The typical way to get an SVD for a matrix $A = UDV^T$ is to compute the eigenvectors of $A^TA$ and $AA^T$. The eigenvectors of $A^TA$ make up the columns of $U$ and the eigenvectors of $AA^T$ make up the column of $V$. From what I've read, the singular values in $D$ are square roots of eigenvalues from $AA^T$ or $A^TA$, and must be non-negative.
However, for the simple example $A = \left[\begin{matrix} 1 & 0 \\ 0 & -1 \end{matrix}\right]$, $A^TA$ and $AA^T$ are both the identity, and thus have eigenvectors $\bigg\lbrace \left[\begin{matrix} 1 \\ 0 \end{matrix}\right]\ ,\ \left[\begin{matrix} 0 \\ 1 \end{matrix}\right]\bigg\rbrace$. Clearly, the eigenvalues are 1 and 1, so our decomposition ought to be:
\begin{align}
 \left[\begin{matrix} 1 & 0 \\ 0 & -1 \end{matrix}\right] = \left[\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}\right]\left[\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}\right]\left[\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}\right]
\end{align}
What has gone wrong?

REPLY [3 votes]: To directly answer your question, the problem is that the "typical way" you describe for getting an SVD is incorrect:

The typical way to get an SVD for a matrix $A = UDV^T$ is to compute the eigenvectors of $A^TA$ $\color{red}{and}$ $AA^T$. The eigenvectors of $A^TA$ make up the columns of $U$ and the eigenvectors of $AA^T$ make up the column of $V$.

One should either give $U$ then solve $V$, or give $V$ then solve $U$ by using the relation $A=UDV^T$.
On the other hand, you wrote that

... and thus have eigenvectors $\bigg\lbrace \left[\begin{matrix} 1 \\ 0 \end{matrix}\right]\ ,\ \left[\begin{matrix} 0 \\ 1 \end{matrix}\right]\bigg\rbrace$

But one could equally have $\bigg\lbrace \left[\begin{matrix} -1 \\ 0 \end{matrix}\right]\ ,\ \left[\begin{matrix} 0 \\ 1 \end{matrix}\right]\bigg\rbrace$, or
$\bigg\lbrace \left[\begin{matrix} 1 \\ 0 \end{matrix}\right]\ ,\ \left[\begin{matrix} 0 \\ -1 \end{matrix}\right]\bigg\rbrace$, or
$\bigg\lbrace \left[\begin{matrix} -1 \\ 0 \end{matrix}\right]\ ,\ \left[\begin{matrix} 0 \\ -1 \end{matrix}\right]\bigg\rbrace$.
Any one of these sets consists of independent eigenvectors (with unit length) of the identity matrix. If one chooses from these sets arbitrarily to form $U$ and $V$, there is no reason to expect that
$$
A=UDV^T.
$$


TITLE: Let $E$ be measurable with $m(E)=1$. Show that there is a measurable set $F\subset E$ such that $m(F)=1/2$.
QUESTION [0 upvotes]: Let $E$ be measurable with $m(E)=1$. Show that there is a measurable set $F\subset E$ such that $m(F)=1/2$. Hint: Consider the function $f(x) = m(E\cap(-\infty,x])$.
I've been working on this but it seems that I am completely stuck. I just started studying real analysis and so I do not have much experience yet but looking at the hint it seems to me I need to show that there is a $x_1$ or which the measure is lower than $1/2$ and one for which it is higher. Then use the continuity to confirm that there is an $x$ for which it takes the value $1/2$. However can't seem to find a way to start doing that. I would prefer hints over complete answers

REPLY [2 votes]: Hint: show that $f$ is continuous, and consider its limits at $\pm\infty$.


TITLE: How to calculate a variable x that produces non-linear results?
QUESTION [1 upvotes]: Sorry I don't have a mathematical background so It is hard for me to put the right words on it.
Let me explain what I am trying to do with an example.
Essentially I want to solve x so that it satisfies both situation:
$100 \times x = 0$
$50 \times x = 3$
I would like to know how to solve this type of equation as well as to know the name of the mathematical concepts involved here.

REPLY [0 votes]: I'm going to interpret your question a little differently, since you yourself say that your mathematical understanding is a bit limited. What I think you want is not a variable $x$ but rather some kind of function $f$ which for the value 100 gives you 0, and for the value 50 gives you 3. I.e., we have
$$f(100) = 0$$
$$f(50) = 3$$
Now, there are infinitely many different functions that would satisfy the two requirements you have. But if we for example stick to the simplest solution, a linear function, the solution would be
$$f(x) = \frac{-3x}{50} + 6$$
From this you can find a new value, for example which one corresponds to 75, by:
$$f(75) = \frac{-3 \cdot 75}{50} + 6 = 1.5$$


TITLE: How to write out the elements of a matrix that has been taken to the $n$th power.
QUESTION [1 upvotes]: I am attempting to write an explicit formula for the individual elements of a matrix that has been exponentiated to the $n$th power. Let $P$ be an $n\times n$ matrix and let $p_{ij}^{(n)}$ be the $(i,j)$th entry of the matrix $P^n$. How can I write out an explicit formula for $p_{ij}^{(n)}$?
I know that $$p_{ij}^{(2)} = \sum_{k=1}^n p_{ik}p_{kj}$$
and I'm fairly sure that
$$p_{ij}^{(3)} = \sum_{r=1}^n p_{rj}\left(\sum_{k=1}^n p_{ik}p_{kj}\right) = \sum_{r=1}^n \sum_{k=1}^np_{rj}p_{ik}p_{kj}$$
But even with this, I'm struggling to generalize for arbitrary $n$. Any help would be appreciated.

REPLY [0 votes]: If your matrix is diagonalizable then we have, $A \in \mathbb{C}^{n \times n} $
$$ A = V \Lambda V^{*}$$
$$ A^{n} = V\Lambda^{n} V^{*} $$
now matrix multiplication is
$$ (AB)_{ik} = \sum_{k=1}^{n} a_{ij}b_{jk} $$
then we have
$$ ((AB)C))_{il} = \sum_{k=1}^{p} \sum_{j=1}^{n} a_{ij}b_{jk} c_{kl} $$
$$ (A)_{il}^{c} =  \sum_{k=1}^{p} \sum_{j=1}^{n} v_{ij} \lambda_{jk}^{c}v_{kl}^{t}$$
now all $ \lambda^{c}  $ is the entries exponentiatied.


TITLE: matrix for frobenius map of finite fields
QUESTION [2 upvotes]: I would be thankful if you could help me :
I have studied many things about Galois fields, but  now I am not sure about my understanding of frobenius maps. For example can anyone help me the matirx of Frobenius map on GF(8) as a vector space over GF(2)?

REPLY [2 votes]: Realising $\Bbb{F}_8$ as $\Bbb{F}_2(\alpha)$ where $\alpha$ is a root of $X^3+X+1$, we have a basis $(1,\alpha,\alpha^2)$ for $\Bbb{F}_8$ over $\Bbb{F}_2$. With respect to this basis the Frobenius map on $\Bbb{F}_8$ is represented by the matrix
$$\left[\begin{array}{ccc}1&0&0\\0&0&1\\0&1&1\end{array}\right].$$
Note that this is very much dependent on the choice of basis for $\Bbb{F}_8$ over $\Bbb{F}_2$.


TITLE: The sequence of functions $u_{n+1}(t)=u_n(t)+\frac{1}{2}(t-u_n^2(t))$ approximates $\sqrt{t}$ from below
QUESTION [1 upvotes]: The square root function on $[0,1]$ is approximated by a sequence of functions (polynomials) defined on $[0,1]$. The induction hypothesis is that you have functions such that
$$0 = u_0\leq u_1\leq ... \leq u_n \leq\sqrt{} \leq 1$$
Through induction it is then said that you can use
$$u_{n+1}(t)=u_n(t)+\frac{1}{2}(t-u_n^2(t))$$
($t$ is the number you want to calculate the square root of) and that $u_{n+1}>u_n$ and $u_{n+1}\leq \sqrt{}$  . I've proved the first statement but after many subsitutions I still can't seem to figure out how to prove that
$u_{n+1}\leq \sqrt{}$

REPLY [1 votes]: You want to prove that $u+\frac12(t-u^2)\le \sqrt{t}$ when $0\le u\le \sqrt{t}$.  The function $f(u)=u+\frac12(t-u^2)$ is increasing because $f'(u)=1-u\ge 0$. Since $f(\sqrt{t})=\sqrt{t}$, the conclusion follows.


TITLE: Calculating the determinant of a matrix
QUESTION [1 upvotes]: During the past week, I have been trying to calculate the determinant of the following matrix:

Here is what I have tried so far. I replaced each row starting from the thrid with the difference of the one before and it. In this way i transformed it into an almost diagonal matrix but still if I try to expand it through the elements of the first column I always get almost diagonal minors and it doesnt work. :(
Please, help me.

REPLY [1 votes]: how about
$$
38\ n!(n+1)!
$$
?
Note that I take
$n=0$ for a $2\times 2$ matrix. For example,
$n=0$
$$
\begin{pmatrix} -8&6\\-9&2\end{pmatrix}
$$
with $\text{det}=38$
$n=1$
$$
\begin{pmatrix} -8&6&6\\-9&2&2\\-9&2&4\end{pmatrix}
$$
with $\text{det}=76=38.2$
$n=2$
$$
\begin{pmatrix}-8&6&6&6\\-9&2&2&2\\-9&2&4&2\\-9&2&2&8\end{pmatrix}
$$
with $\text{det}=456=28.2.6$
$n=3$: $$\begin{pmatrix}-8&6&6&6&6\\-9&2&2&2&2\\-9&2&4&2&2\\-9&2&2&8&2\\-9&2&2&2&14\end{pmatrix}$$, with $\text{det}=5472=38.6.24$.
etc.


TITLE: consolidating terms with conditional probability
QUESTION [0 upvotes]: problem:

A coin is biased so that P(H) = .6. Toss it 10 times. Find the probability of at least 9 heads given that you got at least 8 heads.

answer key (in part):

P(at least 9H | at least 8H) = $\frac{P(at\ least\ 9H\ and\ at\ least\ 8H)}{P(at\ least\ 8H)}$ = $\frac{P(at\ least\ 9H)}{P(at\ least\ 8H)}$

I don't understand how the numerator simplifies here. If anything, I would have expected P(at least 8H) since P(8H or 9H or 10H) includes P(9H or 10H).

REPLY [2 votes]: P(8H or 9H or 10H) includes P(9H or 10H)

or more precisely

(8H or 9H or 10H) includes (9H or 10H)

Yes, and therefore saying that both occur simultaneously is the same as saying the second occurs.


TITLE: If $f(x)=\sqrt{x+a}+\sqrt{b-x}$, find the minimum and maximum values of $f(x)$.
QUESTION [0 upvotes]: If $f(x)=\sqrt{x+a}+\sqrt{b-x}$, find the minimum and maximum values
  of $f(x)$.

According to the AM-GM inequality, the minimum value of $f(x)$ occurs when $\sqrt{x+a}=\sqrt{b-x}$ or $x=\frac{b-a}{2}$. However, assigning random values to $a$ and $b$ and plotting the graph reveals that this is actually the maximum value. What is the reason for this anomaly ?
Example :
If $f(x)=\sqrt{x+1}+\sqrt{3-x}$, the minimum value should be when $x=1$, when $f(1)=2\sqrt{2}$. However, this is actually the maximum value. And the minimum value can be obtained by simply adding the two terms, ignoring the root and then taking the root of the sum.
$$
\sqrt{x+1}+\sqrt{3-x} \ge\sqrt{4}
$$
My second question is, does this always hold true ? In other words, is the following relation always true ?
$$
\sqrt{a+b} \le \sqrt{x+a}+\sqrt{b-x}\le \sqrt{2(a+b)}
$$

REPLY [0 votes]: Here's the thing... You're going to have a restricted domain because this is a $\sqrt{*}$ based function.
You need $x-a>0$ and $b-x>0$ so $x>a \cap x<b$. So first of all you HAVE to guarantee $a<b$
Assuming $a<b$, then you're going to have a function looking like $\cap$, with a maximum in the middle $x=(b-a)/2$ and minimums at the endpoints $x=a \land x=b$
(Try graphing some of them so you get the idea of how to work it out!)
For the maximum you can easily prove it by using an analytic approach
$f(x) = \sqrt{x-a} + \sqrt{b-x}$
$f'(x) = 1/(2*\sqrt{x-a}) - 1/(2*\sqrt{b-x})$
Get the critical point for max/min analysis
$f'(x) = 0 = 1/(2*\sqrt{x-a}) - 1/(2*\sqrt{b-x})$
$\Rightarrow 1/(2*\sqrt{x-a}) = 1/(2*\sqrt{b-x})$
$\Rightarrow {x-a} = {b-x}$
$\Rightarrow x=(b-a)/2$
(you can use $f''(x)$ analysis to prove it is a maximum or do it by analyzing a neighborhood, etc)
As far as proving the minimums, you need to do some more proof magic.
I would to this by proving that f is strictly increasing on $[a,(b-a)/2]$ and decreasing on $[(b-a)/2, b]$ and then you're done.


TITLE: Rieman integration
QUESTION [1 upvotes]: For this question, I think I need to use the fact that this function is continuous. But, how do I know that?

Let $f$ be the function on $[0,1]$ given by
  $$
f(x) = \begin{cases}
0, & 0 \le x < 1\\
1, & 1 \le x < 2\\
2, & 2 \le x < 3\\
\end{cases}
$$

Prove that $f$ is Riemann integrable without appealing to any theorems in this section
Which theorems in this section guarantee that $f$ is Riemann integrable?
What is $\int_0^3 f(x) dx$?

Also, how is it possible to prove that this function is Riemann integrable without using any theorems.
Using that the function is continuous, we could say $U_p(f)-L_p(f) \le \epsilon$ just by saying $|x_n-x_{n-1}|\le \epsilon/3$. And, how do we calculate the integral of it? Is $U_p(f)- L_p(f)$ equal to the integral of f?
Thank you
P.S: Every bounded monotone function on a closed interval is Riemann integrable according to the theorem. I cannot find a theorem to show that this function is Riemann integrable because I am not so sure that this function is monotone. Is it monotone increasing?

REPLY [0 votes]: Probably you have to use the definition of Riemann Integral and try to calculate
$$\sup\{L(f,P):\ P\text{ is a partition of }[0,3]\}$$
and
$$\inf\{U(f,P):\ P\text{ is a partition of }[0,3]\}.$$
I guess that any upper and lower rieman sum will be always the same number, namely, the intergal.
EDIT: at least, you always can add the discontinuity point to your partition to get always the same number. Just an idea.
EDIT2:
Let $P$ be any partition of $[0,3]$. Let $P_0:=P\cup\{1,2\}$. It is clear that $P_0$ is finer than $P$, hence $U(f,P)\ge U(f,P_0)$. But a simple calculation says that $U(f,P_0)=3=\int_0^3 f(x)dx$.
So $$3\le \inf\{U(f,P):\ P\text{ is a partition of }[0,3]\}\le U(f,\{0,1,2,3\})=3.$$
Analogously, you work with $L(f,P)$ and you are done.
It is very easy to get the other inequality


TITLE: Applying Bolzano-Cauchy theorem with infinities
QUESTION [1 upvotes]: So the whole problem that I'm trying to solve simply states: analyse the following function and sketch its graph:
$$f(x) = -x + \ln(\frac{|x|-1}{x})$$
The thing that's problematic here is determining the sign of the function and its zeroes. Solving the equation:
$$-x + \ln(\frac{|x|-1}{x}) = 0$$ seems rather difficult, if not impossible. So I came up with an idea using which I got an approximately correct answer but I'm not sure how "legal" it is.
So the domain of the functions is:
$$ Df: (-1, 0) \cup (1, + \infty)$$
Let's first look at the left side, the one that goes from -1 to 0.
$$\lim_{x \to -1^+}f(x) = \lim_{x \to -1^+}(-x + \ln(\frac{-x-1}{x}))= -1+\lim_{x \to -1^+}{\ln(\frac{-x-1}{x})} = -1 + \ln(\frac{1^- - 1}{-1^+}) = -1 + \ln(\frac{0^-}{-1^+}) = -1 + \ln(0) = -1 - \infty = - \infty$$
I did the similar thing for the right bound of the interval
$$\lim_{x \to 0^-}{f(x)} = \lim_{x \to 0^-}{\ln(\frac{-x-1}{x})} = \ln(\frac{0^+-1}{0^-}) = \ln(\frac{-1}{0^-}) = \ln(\infty) = \infty$$
So basically I got:
$$ \text{as $x \to -1^+$, $f(x) \to -\infty$<0} \\ \text{as $x \to 0^-$, $f(x) \to +\infty$>0} $$
And since the function is obviously continuous on the interval $$(-1, 0)$$ could I somehow use the Bolzano-Cauchy mid-value theorem to state that
$$\forall C \in (-\infty, +\infty) \quad \exists c : f(c) = C $$
And then simply set $$ C = 0$$ thereby concluding that the function must intersect the x axis on $$ (-1, 0) $$ at the same time finding that before that value it's negative and after that value it's positive.
Now this is actually correct, I mean I've looked at the graph of this function and it does indeed intersect the x axis in between -1 and 0. But I'm wondering how legal was my application of the Bolzano-Cauchy theorem here, since the theorem clearly requires that the function be continuous on a closed interval and it also requires that the value at one side of the interval be less than the value at the other side of the interval; but in my case the function isn't even defined at those points.
So did I just get lucky here or is there some justification (some other theorem maybe) for the way I've gotten to my solution.
Also if anyone has any other ideas how to figure out the sign and zeros of this function, that would also be nice.
Thanks.

REPLY [1 votes]: Your reasoning is correct.  Notice that, by definition, $\lim_{x \to 0^-} f(x) = +\infty$ means that for all $M$, there exists a $\delta > 0$ such that $0 < 0 - x < \delta$ implies that $f(x) > M$.  On the other hand, $\lim_{x \to -1^+} f(x)$ means that for all $N$, there exists an $\eta > 0$ such that for $0 < x + 1 < \eta$ implies that $f(x) < - N$.
Now, fix $C$ and choose $N = M = 2|C| + 1$.  Then, choosing the $\delta$ and $\eta$ from the definitions gives us that $f(-1 + \eta/2) < -2|C|$ and $f(- \delta/2) > 2|C|$.  By applying the Bolzano-Cauchy theorem (better known as the Intermediate Value Theorem) to the interval $[-1 + \eta/2, -\delta/2]$, we see that there must exist a $c$ with $-1 < -1 + \eta/2 < c < - \delta < 0$ such that $f(c) = C$.

Do notice, however, that you need a little more information to conclude that $f$ is positive to the right of $c$ and left to the left of $c$: this means that $f$ is increasing over $(-1, 0)$ (and strictly increasing near $0$).  You can justify this by taking there derivative of $f$ and noticing that it is positive over this interval.


TITLE: How can I show that $\lvert \lvert A\rvert \rvert< 1$ in order to prove that $Id-A$ is invertible
QUESTION [1 upvotes]: For a Banach space $X$, I was able to prove that
for $T \in BL(X)$ with $\lvert \lvert T\rvert \rvert < 1$ then $(Id-T)$ is invertible in $BL(X)$.
Defining $A: C([a,b])\to C([a,b])$ where $(Af)(t)=\int\limits_{t_{0}}^{t}ds h(s)f(s)$ where  $C([a,b])$ is equipped with $\lvert \lvert \cdot \rvert \rvert_{\infty}$ and $h \in C([a,b])$, then I also proved that for any $n \in \mathbb N$:
$$\lvert\lvert A^{n}\rvert\rvert \leq \frac{\lvert b-a\rvert^{n}}{n!}\lvert \lvert h\rvert \rvert_{\infty}(*)$$
Question: For any $G \in C([a,b])$ there is a unique $f \in C([a,b])$ such that $(Id-A)f=G$.
This is clearly a question of proving that $\lvert \lvert A\rvert \rvert < 1$ so that I can then use the previous theorem that $(Id-A)$ is invertible. My problem is I cannot seem to find why $\lvert \lvert T\rvert \rvert < 1$ and I do not see how $(*)$ helps me. Any ideas/hints?

REPLY [1 votes]: An overkill solution would be to use the Gelfand formula, which states that
$$
\rho(A) =\lim_n \|A^n\|^{1/n}
$$
where the spectral radius $\rho(A)$ is defined as the supremum of the absolute values of all $x$ such that
$$
x\text{Id}-A
$$
does not have a bounded inverse. In particular, for your $A$, the spectral radius vanishes, as per your bound.
Note: if your operator were diagonalizable, then you'd have $\|A^n\|^{1/n}=\|A\|=\rho(A)$. Non exponential decay of the operator norm shows your operator is not diagonalizable. The statement above says that, even more, it does not have any eigenvalue at all.


TITLE: What does the equation $x^2+24xy+68y^2=0$ represent?
QUESTION [4 upvotes]: The equation $x^2+24xy+68y^2=0$ represents a

Ellips
Parabola
Hyperbola
Can't be decided

I know the general equations of all of these geometric figures, but I can't rework the given equation to match any of them. Completing the square w.r.t. $x$, I get $$(x+12y)^2-76y^2 = 0,$$
but it's still not on any desired form.

REPLY [5 votes]: Completing the square w.r.t $x$ i get $$(x+12y)^2-76y^2 \color{red}{=0}$$

This is a good step; now rewrite using $a^2-b^2 = (a-b)(a+b)$ to get:
$$\left(x+12y + \sqrt{76}y \right)\left(x+12y - \sqrt{76}y \right)=0$$
But this implies:
$$x+12y + \sqrt{76}y = 0 \;\vee\; x+12y - \sqrt{76}y = 0$$
And these are equations of...?


TITLE: Let $A$ be a torsion abelian group. Then $A$ has no $p$-torsion iff $A \otimes \Bbb Z_{(p)} = 0$.
QUESTION [1 upvotes]: Let $A$ be a torsion abelian group, $p$ a prime. Then $A$ has no $p$-torsion iff $A \otimes \Bbb Z_{(p)} = 0$.
I could prove one directioin $\Rightarrow$. But how does one prove the converse?

REPLY [3 votes]: Lets consider the exact sequence $0\rightarrow T\rightarrow A\xrightarrow{\times p} A\rightarrow Q\rightarrow 0$, where $T$ is our $p$ torsion, and $Q$ is the quotient. Tensoring with $\mathbb{Z}_{(p)}$ is exact, so we have the following exact sequence:
$0\rightarrow T\otimes \mathbb{Z}_{(p)}\rightarrow A\otimes \mathbb{Z}_{(p)}\xrightarrow{\times p} A\otimes \mathbb{Z}_{(p)}\rightarrow Q\otimes \mathbb{Z}_{(p)}\rightarrow 0$.
Since $T$ is $p$-torsion, every $n$ coprime to $p$ already acts invertibly on $T$, so this left term is just $T$. So we see that if $A\otimes \mathbb{Z}_{(p)}$ is zero, then $T$ must be zero by exactness, giving the other direction.


TITLE: Calculating the module of a vector in space
QUESTION [0 upvotes]: A) The vectors $\vec{a}$ and $\vec{b}$ makes a $45°$ angle, and the module of $\vec{a}$ is 3. Determine the module of $\vec{b}$ so that the vector $\vec{a} - \vec{b}$ is perpendicular to $\vec{a}$.
Well, I tried using the dot product, because
$$\langle \vec{a}; \vec{b} \rangle = ||\vec{a}||.||\vec{b}||.cos(45°)$$
$$\langle \vec{a}; \vec{b} \rangle = 3.\frac{\sqrt {2}}{2} ||\vec{b}||$$
And then I also know that:
$$\langle \vec{a-b}; \vec{a} \rangle =0$$
But then I don't know what to do with that... I mean, I don't know what to do with the information given but the things that I've written.

REPLY [1 votes]: All you need to do is evaluate the scalar product further:
$$ \langle \vec{a} - \vec{b}, \vec{a} \rangle = \langle \vec{a} , \vec{a} \rangle - \langle \vec{b}, \vec{a} \rangle = ||\vec{a}||^2 - \frac{3 \sqrt{2}}{2} ||\vec{b}|| = 0$$ and solve for $||\vec{b}||$.


text:
\appendix
\section{Proof of Theorem~1}
We repeat the statement of the theorem as follows:

\begin{Theorem*} \label{thm:main_app}
Under  A\ref{ass:bd} and  A\ref{ass:fr}, we denote  by $( \prm^\star, \{ {\bm w}_i^\star \}_{i=1}^N )$ the
primal-dual optimal solution to the optimization problem in \eqref{eq:opt_pd}. Set the
step sizes as $\gamma_2 = \beta \gamma_1 $ with
$\beta \eqdef 8 ( \rho + \lambda_{\sf max} ( \hat{\bm A}^\top \hat{\bm C}^{-1} \hat{\bm A}) ) / \lambda_{\sf min}( \hat{\bm C})$.
Define $\overline{\prm}(t) \eqdef \frac{1}{N} \sum_{i=1}^N \prm_i^t$ as
the average of parameters.
If the primal step size $\gamma_1$ is sufficiently small, then
there exists a constant $0 < \sigma < 1$ that
\beq \label{eq:converge} \notag
\textstyle
\big\| \overline{\prm}(t) - \prm^\star \big\|^2 + (1/\beta N) \sum_{i=1}^N \big\| {\bm w}_i^t - {\bm w}_i^\star \big\|^2 = {\cal O}( \sigma^t ),~~  (1/N) \sum_{i=1}^N \big\| \prm_i^t - \overline{\prm}(t) \big\| = {\cal O}( \sigma^t ) \eqs.
\eeq
If $N,M \gg 1$ and the graph is geometric with $\lambda = 1 - c/N$ for  $c>0$, a sufficient condition for convergence
is to set $\gamma = {\cal O}(1/ \max\{N^2,M^2\})$ and the resultant rate
is $\sigma = 1 - {\cal O}( 1/ \max\{M N^2, M^3\})$.
\end{Theorem*}

\paragraph{Notation}
We first define a set of notations pertaining to the proof.
For any $\beta > 0$, observe that the primal-dual optimal solution,
$(  \prm^\star, \{ {\bm w}_i ^{\star}\}_{i=1}^N )$,
to the optimization problem  \eqref{eq:opt_pd} can be written as
\beq \label{eq:opt_cond}
\underbrace{\left(
\begin{array}{cccc}
\rho {\bm I} & \sqrt{\frac{\beta}{N}} \hat{\bm A}^\top & \cdots & \sqrt{\frac{\beta}{N}} \hat{\bm A}^\top \\
-\sqrt{\frac{\beta}{N}} \hat{\bm A} & \beta \hat{\bm C} & \cdots & \cdots \\
\vdots & {\bm 0} & \ddots & {\bm 0} \\
-\sqrt{\frac{\beta}{N}} \hat{\bm A} & \cdots & \cdots & \beta \hat{\bm C}
\end{array}
\right)}_{\eqdef {\bm G}}
\left( \begin{array}{c}
\prm^\star \\
\frac{1}{\sqrt{\beta N}}{\bm w}_1^\star \\
\vdots \\
\frac{1}{\sqrt{\beta N}}{\bm w}_N^\star
\end{array}
\right)
=
\left( \begin{array}{c}
{\bm 0} \\
-\sqrt{\frac{\beta}{N}}{\bm b}_1 \\
\vdots \\
-\sqrt{\frac{\beta}{N}}{\bm b}_N
\end{array}
\right) \eqs,
\eeq
where we  denote the matrix on the left hand side as ${\bm G}$.  This equation can be obtained by checking the first-order optimality condition. In addition, for any $p \in \{ 1, \ldots, M \}$, we  define the  ${\bm G}_p$ as
\beq\label{eq:matrix_Gp}
{\bm G}_p \eqdef \left(
\begin{array}{cccc}
\rho {\bm I} & \sqrt{\frac{\beta}{N}} {\bm A}_p^\top & \cdots & \sqrt{\frac{\beta}{N}} {\bm A}^\top \\
-\sqrt{\frac{\beta}{N}}{\bm A}_p & \beta {\bm C}_p & \cdots & \cdots \\
\vdots & {\bm 0} & \ddots & {\bm 0} \\
-\sqrt{\frac{\beta}{N}}{\bm A}_p & \cdots & \cdots & \beta {\bm C}_p
\end{array}
\right) \eqs.
\eeq
By definition, ${\bm G}$ is the sample average of $ \{ {\bm G}_p \}_{p=1}^M$.
Define $\bar{\prm}(t) \eqdef (1/N) \sum_{i=1}^N \prm_i^t$ as the average of the local parameters at iteration $t$. Furthermore, we define
\begin{align}
	{\bm h}_{\prm}(t)  \eqdef \rho \bar{\prm}(t) + \frac{1}{N} \sum_{i=1}^N \hat{\bm A}^\top {\bm w}_i^t, & \qquad {\bm g}_{\prm}(t) \eqdef \frac{1}{NM} \sum_{i=1}^N \sum_{p=1}^M \big( \rho \prm_i^{\tau_p^t} + {\bm A}_p^\top {\bm w}_i^{\tau_p^t} \big)  \eqs, \label{eq:4terms_1}  \\
	{\bm h}_{ {\bm w}_i } (t) \eqdef \hat{\bm A} \bar{\prm}(t) - \hat{\bm C} {\bm w}_i^t - \hat{\bm b}_i, & \qquad
	{\bm g}_{ {\bm w}_i } (t) \eqdef \frac{1}{M} \sum_{p=1}^M \big( {\bm A}_p \prm_i^{\tau_p^t} - {\bm C}_p {\bm w}_i^{\tau_p^t} - {\bm b}_{p,i} \big) \eqs, \label{eq:4terms_2}
\end{align}
where ${\bm h}_{\prm}(t)$ and $ {\bm h}_{\bm w}(t) : = [{\bm h}_{ {\bm w}_1} (t), \cdots, 	{\bm h}_{ {\bm w}_N } (t)]$ represent the gradients evaluated by a \emph{centralized} and
\emph{batch} algorithm.
Note that ${\bm g}_{\prm}(t)$ defined in \eqref{eq:4terms_1} coincides with that in \eqref{eq:track}.
Using Lemma~\ref{lem:avg},
it can be checked that $\bar{\prm}(t+1) = \bar{\prm}(t) - \gamma_1 {\bm g}_{\prm}(t)$
and ${\bm w}_i^{t+1} = {\bm w}_i^t - \gamma_2 {\bm g}_{ {\bm w}_i } (t)$
for all $t \geq 1$.
That is, $\bar{\prm}(t+1)$ and ${\bm w}_i^{t+1} $ can be viewed as primal-dual updates using  ${\bm g}_{\prm}(t)$ and ${\bm g}_{ {\bm w}_i } (t)$, which are decentralized counterparts of gradients ${\bm h}_{\prm}(t)$ and ${\bm h}_{ {\bm w}_i} (t)$ defined in \eqref{eq:4terms_1} \eqref{eq:4terms_2}.

To simplify the notation, hereafter, we define  vectors $\underline{\bm h}(t)$, $\underline{\bm g}(t)$, and $\underline{\bm v}(t) $ by
\beq \label{eq:define_3vectors}
\underline{\bm h}(t) \eqdef \left( \begin{array}{c}
 {\bm h}_{\prm}(t) \\
-\sqrt{\frac{\beta}{N}} {\bm h}_{ {\bm w}_1 } (t) \\
\vdots \\
-\sqrt{\frac{\beta}{N}} {\bm h}_{ {\bm w}_N } (t)
\end{array}
\right),~
\underline{\bm g}(t) \eqdef \left( \begin{array}{c}
 {\bm g}_{\prm}(t) \\
-\sqrt{\frac{\beta}{N}} {\bm g}_{ {\bm w}_1 } (t) \\
\vdots \\
-\sqrt{\frac{\beta}{N}} {\bm g}_{ {\bm w}_N } (t)
\end{array}
\right),~
\underline{\bm v}(t) \eqdef
\left( \begin{array}{c}
\bar{\prm}(t) - \prm^\star \\
\frac{1}{\sqrt{\beta N}} \big( {\bm w}_1^t - {\bm w}_1^\star \big) \\
\vdots \\
\frac{1}{\sqrt{\beta N}} \big( {\bm w}_N^t - {\bm w}_N^\star \big)
\end{array}
\right) \eqs.
\eeq
Using \eqref{eq:opt_cond}, it can be verified that (see the detailed  derivation in
Section~\ref{sec:detailed})
\beq \label{eq:new_equality}
\underline{\bm h}(t) = {\bm G} \underline{\bm v}(t) \eqs.
\eeq

By adopting the analysis in \citep{du2017stochastic} and under
Assumption \ref{ass:fr}, it can be shown that with
\beq\notag
\beta \eqdef \frac{ 8 ( \rho + \lambda_{\sf max} \bigl [  \hat{\bm A}^\top \hat{\bm C}^{-1} \hat{\bm A} )  \bigr ]}{ \lambda_{\sf min}( \hat{\bm C}) } \eqs,
\eeq
then ${\bm G}$ is full rank with its eigenvalues satisfying
\beq\label{eq:eigen_G}
\lambda_{\sf max} ( {\bm G} ) \leq \left| \frac{\lambda_{\sf max} ( \hat{\bm C} ) }{
\lambda_{\sf min} (\hat{\bm C} )} \right| \lambda_{\sf max} ( \rho {\bm I} + \hat{\bm A}^\top \hat{\bm C}^{-1} \hat{\bm A} ),\qquad
\lambda_{\sf min} ( {\bm G} ) \geq \frac{8}{9} \lambda_{\sf min} ( \hat{\bm A}^\top \hat{\bm C}^{-1} \hat{\bm A} ) > 0 \eqs.
\eeq
Moreover,  let
$
{\bm G} \eqdef {\bm U} \bm{\Lambda} {\bm U}^{-1} \eqs.
$
be the eigen-decomposition of ${\bm G}$, where ${\bm \Lambda}$ is  a diagonal matrix consists of the eigenvalues of ${\bm G}$, and the columns of ${\bm U}$ are the eigenvectors.
Then,  ${\bm U}$ is full rank with
\beq\label{eq:eigen_U}
\| {\bm U} \| \leq 8 \bigl [  \rho + \lambda_{\sf max} ( \hat{\bm A}^\top \hat{\bm C}^{-1} \hat{\bm A} ) \bigr ]\left| \frac{\lambda_{\sf max} ( \hat{\bm C} ) }{
\lambda_{\sf min} (\hat{\bm C} )} \right| ,\qquad \| {\bm U}^{-1} \| \leq \frac{1}{ \rho + \lambda_{\sf max} ( \hat{\bm A}^\top \hat{\bm C}^{-1} \hat{\bm A} )} \eqs.
\eeq

Furthermore, we also define the following upper bounds on the spectral norms
\beq\label{eq:norm_bounds}
G \eqdef \| {\bm G} \|, \quad \overline{G} \eqdef \max_{p=1,...,M} \| {\bm G}_p \|,\quad \overline{A} \eqdef \max_{p=1,...,M} \| {\bm A}_p \|, \quad \overline{C} \eqdef \max_{p=1,...,M} \| {\bm C}_p \| \eqs.
\eeq
Lastly, we define the following two Lyapunov functions
\beq \label{eq:lya_funcs}
{\cal E}_c(t) \eqdef \frac{1}{N}  \biggl [ \sum_{i=1}^N \| \prm_i^t - \overline{\prm}(t) \|^2 \biggr ]^{1/2 } ,\qquad {\cal E}_g(t) \eqdef \frac{1}{N} \biggl [ \sum_{i=1}^N  \| {\bm s}_i^t - {\bm g}_{\prm}(t) \|^2 \biggr ] ^{1/2} \eqs.
\eeq
Note that we have the following inequalities:
\beq \label{eq:equiv_norm}
 {\cal E}_c(t) \leq \frac{1}{N} \sum_{i=1}^N \| \prm_i^t - \overline{\prm}(t) \|,~~\frac{1}{N}\sum_{i=1}^N \| \prm_i^t - \overline{\prm}(t) \| \leq \sqrt{N} {\cal E}_c(t) \eqs,
\eeq
which follows from the norm equivalence $\| {\bm x} \|_2 \leq \| {\bm x} \|_1 \leq \sqrt{N} \| {\bm x} \|_2$ for any ${\bm x} \in \RR^N$.

\paragraph{Convergence Analysis}
We denote that $\gamma_1 = \gamma$ and $\gamma_2 = \beta \gamma$.
To study the linear convergence of the {\sf PD-DistIAG} method,
our first step is to establish a bound on the difference
from the primal-dual optimal solution,
$\underline{\bm v}(t)$. Observe with the choice of our step size ratio,
\beq \label{eq:taking_norm}
\underline{\bm v}(t+1) = ( {\bm I} - \gamma {\bm G} ) \underline{\bm v}(t) + \gamma \big[  \underline{\bm h}(t) - \underline{\bm g}(t) \big]  \eqs.
\eeq
Consider the difference vector
$\underline{\bm h}(t) - \underline{\bm g}(t)$. Its first block can be evaluated as
\beq \label{eq:last1}
\begin{split}
& \big[ \underline{\bm h}(t) - \underline{\bm g}(t) \big]_1
 = \frac{1}{NM} \sum_{i=1}^N \sum_{p=1}^M \Big[ \rho \big( \bar{\prm}(t) - \prm_i^{\tau_p^t} \big)
+ {\bm A}_p^\top \big( {\bm w}_i^t - {\bm w}_i^{\tau_p^t} \big) \Big] \\
& = \frac{1}{NM} \sum_{i=1}^N \sum_{p=1}^M \Big[  \rho \big( \bar{\prm}(t) - \bar{\prm} (\tau_p^t) \big)
+ {\bm A}_p^\top \big( {\bm w}_i^t - {\bm w}_i^{\tau_p^t} \big) \Big]
+ \frac{\rho}{NM} \sum_{i=1}^N \sum_{p=1}^M \big( \bar{\prm}( \tau_p^t) - \prm_i^{\tau_p^t} \big) \eqs.
\end{split}
\eeq
Meanwhile, for any $i \in \{ 1, \ldots, N\}$,  the $(i+1)$-th block  is
\begin{align} \label{eq:last2}
& \big[ \underline{\bm h}(t) - \underline{\bm g}(t) \big]_{i+1}
 = \sqrt{\frac{\beta}{N}} \frac{1}{M} \sum_{p=1}^M \Big[  {\bm A}_p \big( \prm_i^{\tau_p^t} - \bar{\prm}(t) \big) + {\bm C}_p \big( {\bm w}_i^t - {\bm w}_i^{\tau_p^t} \big) \Big] \\
 & =
 \sqrt{\frac{\beta}{N}} \frac{1}{M} \sum_{p=1}^M \Big[ {\bm A}_p \big( \bar{\prm} (\tau_p^t) - \bar{\prm}(t) \big) + {\bm C}_p \big( {\bm w}_i^t - {\bm w}_i^{\tau_p^t} \big) \Big]
 + \sqrt{\frac{\beta}{N}} \frac{1}{M} \sum_{p=1}^M {\bm A}_p \big( \prm_i^{\tau_p^t} - \bar{\prm}( \tau_p^t ) \big) \eqs. \notag
\end{align}
For ease of presentation, we stack up and denote the residual terms (related to consensus error)
in \eqref{eq:last1} and \eqref{eq:last2}
as the vector $\underline{\bm{\mathcal{E}}}_c(t)$.
That is, the first block of $\underline{\bm{\mathcal{E}}}_c(t)$ is $\rho / (  NM) \cdot \sum_{i=1}^N \sum_{p=1}^M \big( \bar{\prm}( \tau_p^t) - \prm_i^{\tau_p^t} \big)$, and the remaining blocks are given by $
 \sqrt{ {\beta} / {N}} \cdot  1 / {M} \cdot  \sum_{p=1}^M {\bm A}_p \big( \prm_i^{\tau_p^t} - \bar{\prm}( \tau_p^t ) \big) $, $\forall i \in \{ 1, \ldots, N\}$.
 Then by the definition of ${\bm G}_p$ in \eqref{eq:matrix_Gp},
we obtain the following simplification:
\beq\label{eq:grad_diff_telescope}
\underline{\bm h}(t) - \underline{\bm g}(t) - \underline{\bm{\mathcal{E}}}_c(t)
= \frac{1}{M} \sum_{p=1}^M {\bm G}_p \Big( {\textstyle \sum_{j=\tau_p^t}^{t-1} \underline{\Delta {\bm v}} (j)} \Big),
\eeq
where we have defined
\beq\label{eq:defineDeltav}
\underline{\Delta {\bm v}} (j) \eqdef
\left( \begin{array}{c}
\bar{\prm}(j+1) - \bar{\prm}(j) \\
\frac{1}{\sqrt{\beta N}} \big( {\bm w}_1^{j+1} - {\bm w}_1^j \big) \\
\vdots \\
\frac{1}{\sqrt{\beta N}} \big( {\bm w}_N^{j+1} - {\bm w}_N^j \big)
\end{array}
\right) \eqs.
\eeq
Clearly, we can express $\Delta \underline{\bm v}(j)$ as
$
\Delta \underline{\bm v}(j) = \underline{\bm v}(j+1) - \underline{\bm v}(j)
$
with $\underline {\bm v}(t)$ defined in \eqref{eq:define_3vectors}.
Combining \eqref{eq:new_equality} and \eqref{eq:taking_norm}, we can also write $\Delta \underline{\bm v}(j) $  in \eqref{eq:defineDeltav} as
\beq\label{eq:some_equation1}
\Delta \underline{\bm v}(j) = \gamma \big[  \underline{\bm h}(j) - \underline{\bm g}(j) \big] - \gamma  \underline{\bm h}(j) \eqs.
\eeq
Denoting $\widehat{\underline{\bm v}}(t) \eqdef {\bm U}^{-1} \underline{\bm v}(t)$, multiplying ${\bm U}^{-1}$ on both sides of \eqref{eq:taking_norm} yields
\beq\label{eq:some_equation2}
\widehat{\underline{\bm v}}(t+1) = ( {\bm I} - \gamma \bm{\Lambda} ) \widehat{\underline{\bm v}}(t) + \gamma~ {\bm U}^{-1} \big( \underline{\bm h}(t) - \underline{\bm g}(t) \big) \eqs.
\eeq
Combining \eqref{eq:grad_diff_telescope}, \eqref{eq:some_equation1}, and \eqref{eq:some_equation2}, by triangle inequality, we have
\begin{align} \label{eq:some_equation3}
& \| \widehat{\underline{\bm v}}(t+1) \|  \leq \\
& \qquad  \big\| {\bm I} - \gamma \bm{\Lambda} \big\|
\| \widehat{\underline{\bm v}}(t) \|
+ \gamma \| {\bm U}^{-1} \| \biggl \{ \|  \underline{\bm{\mathcal{E}}}_c(t) \|
 + \frac{\gamma \overline{G}}{M} \sum_{p=1}^M \sum_{j=\tau_p^t}^{t-1} \big [  \| \underline{\bm h}(j) \| + \| \underline{\bm h}(j) - \underline{\bm g}(j) \| \big ]  \bigg \} \eqs, \notag
\end{align}
where $\overline {G} $ appears in \eqref{eq:norm_bounds} and $\underline{\bm{\mathcal{E}}}_c(t)$ is the residue  term of the consensus.
Furthermore, simplifying the right-hand side of \eqref{eq:some_equation3} yields
\begin{align} \label{eq:bound_v_norm_upper}
& \| \widehat{\underline{\bm v}}(t+1) \|   \leq \big\| {\bm I} - \gamma \bm{\Lambda} \big\|
\| \widehat{\underline{\bm v}}(t) \|
+ \gamma \|{\bm U}^{-1}\| \biggl \{ \|  \underline{\bm{\mathcal{E}}}_c(t) \|
 + \gamma \overline{G} \sum_{j=(t-M)_+}^{t-1} \big[   \| \underline{\bm h}(j) \| + \| \underline{\bm h}(j) - \underline{\bm g}(j) \| \big ]  \biggr  \}   \notag \\
 & \qquad  \leq \big\| {\bm I} - \gamma \bm{\Lambda} \big\|
\| \widehat{\underline{\bm v}}(t) \|
+ \gamma \| {\bm U}^{-1} \| \Bigg( \|  \underline{\bm{\mathcal{E}}}_c(t) \| + \gamma \overline{G}  \cdot \\
& \qquad \qquad  \sum_{j=(t-M)_+}^{t-1} \bigg \{  \|  \underline{\bm{\mathcal{E}}}_c(j) \| + G \| {\bm U} \| \| \widehat{\underline{\bm v}}(j) \| +
\overline{G}  \| {\bm U} \|  \sum_{\ell=(j-M)_+}^{j-1}  \bigl [  \| \widehat{\underline{\bm v}}(\ell+1) \| + \| \widehat{\underline{\bm v}}(\ell) \|  \bigr ]
 \bigg\}  \Bigg)  \eqs. \notag
\end{align}

Moreover, using the definition and \eqref{eq:equiv_norm}, we can
upper bound  $\| \underline{\bm{\mathcal{E}}}_c(t) \|$ by
\beq\label{eq:Ec_bound}
\| \underline{\bm{\mathcal{E}}}_c(t) \| \leq \frac{ 1 }{ M } \sum_{p=1}^M \bigg[
\big( \rho + \overline{A} \sqrt{\beta N} \big)  \frac{1}{N} \sum_{i=1}^N
\| \prm_i^{\tau_p^t} - \bar{\prm} ( \tau_p^t ) \|  \bigg]
\leq
\sqrt{N} \big( \rho + \overline{A} \sqrt{\beta N} \big) \max_{ (t-M)_+ \leq q \leq t } {\cal E}_c(q)  \eqs .
\eeq
Thus, combining \eqref{eq:bound_v_norm_upper} and  \eqref{eq:Ec_bound}, we bound $\| \widehat{\underline{\bm v}}(t+1)  \| $ by
\beq \label{eq:v_1}
 \| \widehat{\underline{\bm v}}(t+1)  \|  \leq
\big\| {\bm I} - \gamma \bm{\Lambda} \big\|
\| \widehat{\underline{\bm v}}(t) \|
+ C_1( \gamma ) \max_{ (t-2M)_+ \leq q \leq t-1 } \| \widehat{\underline{\bm v}}(q) \|
+ C_2( \gamma ) \max_{ (t-2M)_+ \leq q \leq t } {\cal E}_c(q) \eqs ,
\eeq
where constants $C_1(\gamma)$ and $C_2(\gamma)$ are given by
\beq\notag
C_1( \gamma )  \eqdef \gamma^2~ \| {\bm U} \|   \| {\bm U}^{-1} \|   \overline{G} M  \big( G + 2 \overline{G} M \big),~ C_2( \gamma ) \eqdef \gamma  \| {\bm U}^{-1}  \| \big( 1 + \gamma\overline{G} M \big) \sqrt{N} \big( \rho + \overline{A} \sqrt{\beta N} \big).
\eeq
Notice that since ${\bm U}^{-1}$ is full rank, the squared norm
$\| \widehat{\underline{\bm v}}(t)  \|^2$ is proportional to
$\| \overline{\prm}(t) - \prm^\star \|^2 + (1/\beta N) \sum_{i=1}^N \| {\bm w}_i^\star - {\bm w}_i^t \|^2$, \ie
the optimality gap at the $t$-th iteration.

We next  upper bound ${\cal E}_c(t+1)$ as defined in \eqref{eq:lya_funcs}. Notice that $N {\cal E}_c(t+1)$ can be written as Frobenius norm of the matrix $\bm{\Theta}^{t+1} - {\bf 1} \overline{\prm}(t+1)^\top$, where $\bm{\Theta}^{t+1} = ( (\prm_1^{t+1})^\top ; \cdots ; (\prm_N^{t+1})^\top )$. Also, we denote ${\bm S}^t = ( ({\bm s}_1^t)^\top; \cdots ({\bm s}_N^t)^\top)$.  By  the   update in \eqref{eq:pd_alg} and using the triangle inequality, we have
\beq \label{eq:fin_c02}
\begin{split}
{\cal E}_c(t+1) & = \frac{1}{N} \| \bm{\Theta}^{t+1} - {\bf 1} \overline{\prm}(t+1)^\top \|_F
= \frac{1}{N} \| {\bm W} ( \bm{\Theta}^{t} - {\bf 1} \overline{\prm}(t)^\top ) - \gamma ( {\bm S}^t - {\bf 1} {\bm g}_{\prm}(t)^\top ) \|_F \\
& \leq \frac{1}{N} \big( \| \bm{\Theta}^{t+1} - {\bf 1} \overline{\prm}(t)^\top \|_F + \gamma \!~\| {\bm S}^t - {\bf 1} {\bm g}_{\prm}(t)^\top \|_F \big) \eqs.
\end{split}
 \eeq
Notice that we have $\lambda \eqdef \lambda_{\sf max}({\bm W} - (1/N) {\bf 1}{\bf 1}^\top ) < 1$ as the graph is connected. Using the fact that $N {\cal E}_g(t) = \| {\bm S}^t - {\bf 1} {\bm g}_{\prm}(t)^\top  \|_F$,

the right-hand side of \eqref{eq:fin_c02} can be bounded by
 \begin{align}\label{eq:fin_c2}
 {\cal E}_c(t+1) & \leq
\lambda ~ {\cal E}_c(t) + \gamma ~ {\cal E}_g(t) \eqs,
\end{align}
where the Lyapunov function ${\cal E}_g(t) $ is defined in \eqref{eq:lya_funcs}.

To conclude the proof, we need to further  upper bound ${\cal E}_g(t+1)$.   To simplify the notation, let us define ${\bm G}_{p}^t = ( \grd_{\prm} J_{1,p} (\prm_1^t;{\bm w}_1^t)^\top; \cdots ;  \grd_{\prm} J_{N,p} (\prm_N^t;{\bm w}_N^t)^\top )$ and observe that
\beq
{\cal E}_g(t+1) = \frac{1}{N} \Big\| {\bm S}^{t+1} - {\bf 1}{\bm g}_{\prm}(t+1)^\top \Big\|_F
= \frac{1}{N} \Big\| {\bm W} {\bm S}^{t} + {\textstyle \frac{1}{M}} \big( {\bm G}_{p_{t+1}}^{t+1} - {\bm G}_{p_{t+1}}^{\tau_{p_{t+1}}^t} \big) - {\bf 1}{\bm g}_{\prm}(t+1)^\top \Big\|_F

\eeq
where we have used \eqref{eq:s_upd}.
Furthermore, we observe
\begin{align} \label{eq:bound_Eg_first}
{\cal E}_g(t+1) & = \frac{1}{N} \Big\| {\bm W} ( {\bm S}^{t} -  {\bf 1} {\bm g}_{\prm}(t)^\top )+ {\textstyle \frac{1}{M}} \big( {\bm G}_{p_{t+1}}^{t+1} - {\bm G}_{p_{t+1}}^{\tau_{p_{t+1}}^t} \big) - {\bf 1}( {\bm g}_{\prm}(t+1) - {\bm g}_{\prm}(t) )^\top \Big\|_F \notag  \\
& \leq \frac{1}{N} \Big( \| {\bm W} ( {\bm S}^t - {\bf 1} {\bm g}_{\prm}(t)^\top ) \|_F + \| {\textstyle \frac{1}{M}} \big( {\bm G}_{p_{t+1}}^{t+1} - {\bm G}_{p_{t+1}}^{\tau_{p_{t+1}}^t} \big) - {\bf 1}({\bm g}_{\prm}(t+1) - {\bm g}_{\prm}(t))^\top \|_F \Big) \notag\\
& \leq \lambda \!~ {\cal E}_g(t) + \frac{1}{N} \Bigl \| {\textstyle \frac{1}{M}} \big( {\bm G}_{p_{t+1}}^{t+1} - {\bm G}_{p_{t+1}}^{\tau_{p_{t+1}}^t} \big) - {\bf 1}({\bm g}_{\prm}(t+1) - {\bm g}_{\prm}(t))^\top \Bigr \|_F \eqs .
\end{align}
We observe
${\bm G}_{p}^t  = (  ({\bm w}_1^t)^\top {\bm A}_p; \cdots ; ({\bm w}_N^t)^\top {\bm A}_p ) + \rho \!~ \bm{\Theta}^t$
and
${\bm g}_{\prm}(t+1) - {\bm g}_{\prm} (t)  = M^{-1} \big( \rho \!~ \bar{\prm}(t+1) - \rho \!~ \bar{\prm}( \tau_{p_{t+1}}^t ) + N^{-1} {\bm A}_{p_{t+1}}^\top \sum_{i=1}^N \big( {\bm w}_i^{t+1} - {\bm w}_i^{\tau_{p_{t+1}}^t} \big) \big)$. Adopting the notations $\bm{\Omega}^t = ( ({\bm w}_1^t)^\top ; \cdots; ({\bm w}_N^t )^\top )$ and $\overline{\bm w}^t = N^{-1} \sum_{i=1}^N {\bm w}_i^t$, we observe that
\beq
\begin{split}
& M^{-1} ( {\bm G}_{p_{t+1}}^{t+1} - {\bm G}_{p_{t+1}}^{\tau_{p_{t+1}}^t} ) - {\bf 1} ( {\bm g}_{\prm}(t+1) - {\bm g}_{\prm}(t) )^\top \\
& \qquad = \frac{\rho}{M} \big( \bm{\Prm}^{t+1} - {\bf 1} \overline{\prm}(t+1)^\top - \bm{\Prm}^{\tau_{p_{t+1}}^t} - {\bf 1} \overline{\prm}(\tau_{p_{t+1}}^t)^\top \big) \\
& \quad \qquad+ \frac{1}{M} \big(
\bm{\Omega}^{t+1} - {\bf 1} (\overline{\bm w}^{t+1})^\top - \bm{\Omega}^{ \tau_{p_{t+1}}^t } + {\bf 1} (\overline{\bm w}^{\tau_{p_{t+1}}^t})^\top \big) {\bm A}_{p_{t+1}} \eqs .
\end{split}
\eeq
Using the triangular inequality,  the norm of the above can be bounded as
\beq
\begin{split}
& \frac{\rho}{M} \Big( \| \bm{\Prm}^{t+1} - {\bf 1} \overline{\prm}(t+1)^\top \|_F + \| \bm{\Prm}^{\tau_{p_{t+1}}^t} - {\bf 1} \overline{\prm}(\tau_{p_{t+1}}^t)^\top \|_F \Big) \\
& \quad + \frac{ \| {\bm A}_{p_{t+1}} \| }{ M } \Big( \| \bm{\Omega}^{t+1} - {\bf 1} (\overline{\bm w}^{t+1})^\top - \bm{\Omega}^{ \tau_{p_{t+1}}^t } + {\bf 1} (\overline{\bm w}^{\tau_{p_{t+1}}^t})^\top \|_F \Big) \eqs.
\end{split}
\eeq
From the norm equivalence $\| {\bm x} \|_2 \leq \| {\bm x} \|_1$, we recognize that
$\| \bm{\Omega}^{t+1} - {\bf 1} (\overline{\bm w}^{t+1})^\top - \bm{\Omega}^{ \tau_{p_{t+1}}^t } + {\bf 1} (\overline{\bm w}^{\tau_{p_{t+1}}^t})^\top \|_F
\leq \sum_{i=1}^N \| {\bm w}_i^{t+1} - \overline{\bm w}^{t+1}
- {\bm w}_i^{\tau_{p_{t+1}}^t } + \overline{\bm w}^{\tau_{p_{t+1}}^t } \|$.
It holds for all
 $t' \leq t$  that
\beq \notag
{\bm w}_i^{t+1} - {\bm w}_i^{t'} = - \frac{\gamma}{ \beta M} \sum_{\ell=t'}^t \sum_{p=1}^M \Big[ {\bm A}_p ( \prm_i^{\tau_p^\ell} - \prm^\star ) - {\bm C}_p ( {\bm w}_i^{\tau_p^\ell} - {\bm w}_i^\star ) \Big]  \eqs .
\eeq
We thus obtain
\begin{align}\label{eq:bound_sum_delta_tt}
& \frac{ \| {\bm A}_{p_{t+1}} \| }{ M } \Big( \| \bm{\Omega}^{t+1} - {\bf 1} (\overline{\bm w}^{t+1})^\top - \bm{\Omega}^{ \tau_{p_{t+1}}^t } + {\bf 1} (\overline{\bm w}^{\tau_{p_{t+1}}^t})^\top \|_F \Big) \notag \\
& \qquad \leq \frac{ \| {\bm A}_{p_{t+1}} \| }{ M } \sum_{i=1}^N
\bigg\| {\bm w}_i^{t+1} - \frac{1}{N} \sum_{j=1}^N {\bm w}_j^{t+1}
- {\bm w}_i^{\tau_{p_{t+1}}^t } + \frac{1}{N} \sum_{j=1}^N {\bm w}_j^{\tau_{p_{t+1}}^t } \bigg\|
\notag \\
&\qquad  \leq
\frac{ 2 \gamma \overline{A} }{ \beta M^2} \sum_{i=1}^N \sum_{\ell = (t-M)_+}^t  \sum_{p=1}^M \Big(
\big \| {\bm A}_p ( \prm_i^{\tau_p^\ell} - \prm^\star ) - {\bm C}_p ( {\bm w}_i^{\tau_p^\ell} - {\bm w}_i^\star ) \big\| \Big)  \notag \\
& \qquad \leq \frac{ 2\gamma \overline{A} }{ \beta M} \sum_{i=1}^N \sum_{\ell = (t-M)_+}^t  \biggl [ \max_{ (\ell-M)_+ \leq q \leq \ell } \Big( \overline{A} \| \prm_i^q - \prm^\star \| + \overline{C} \| {\bm w}_i^q - {\bm w}_i^\star \| \Big) \biggr ] \eqs.
\end{align}
Thus, combining \eqref{eq:fin_c2},
\eqref{eq:bound_sum_delta_tt}, and the definition of ${\cal E}_c$ in \eqref{eq:lya_funcs}, we have
\begin{align}  \label{eq:bound_delta_avg}
 & \textstyle  \frac{1}{N} \| {\textstyle \frac{1}{M}} \big( {\bm G}_{p_{t+1}}^{t+1} - {\bm G}_{p_{t+1}}^{\tau_{p_{t+1}}^t} \big) - {\bf 1}({\bm g}_{\prm}(t+1) - {\bm g}_{\prm}(t))^\top \|_F \\
 & \notag \leq \frac{\rho}{M} \bigl [  {\cal E}_c ( \tau_{p_{t+1}}^t ) + {\cal E}_c(t+1)  \bigr ] \\
 & \qquad \qquad  +  \frac{ 2 \gamma \overline{A} (M+1) }{ \beta NM} \sum_{i=1}^N
\max_{ (t-2M)_+ \leq q \leq t } \Big( \overline{A} \| \prm_i^q - \prm^\star \| + \overline{C} \| {\bm w}_i^q - {\bm w}_i^\star \| \Big)  \notag \\
&   \leq   \frac{ \rho }{M} \bigl [  {\cal E}_c ( \tau_{p_{t+1}}^t )
+ \lambda  \!~ {\cal E}_c ( t ) + \gamma~ {\cal E}_g ( t ) \bigr ] \notag \\
& \notag \qquad   + \frac{ 2 \gamma \overline{A} (M+1) }{ \beta M}
\max_{ (t-2M)_+ \leq q \leq t } \Big( \overline{A}~\sqrt{N} {\cal E}_c(q) + \overline{A}~\| \bar{\prm}(q) - \prm^\star\|  + \frac{ \overline{C} }{N} \sum_{i=1}^N \| {\bm w}_i^q - {\bm w}_i^\star \| \Big) \eqs.
\end{align}
Combining \eqref{eq:bound_Eg_first} and \eqref{eq:bound_delta_avg}, we obtain that \beq
\begin{split}\label{eq:final_bound_Eg2}
& {\cal E}_g(t+1)  \leq \Big( \lambda + \frac{ \gamma \rho }{M} \Big) ~{\cal E}_g( t) + \bigg[
\frac{ 2 \gamma \overline{A}^2 (M+1) \sqrt{N} }{\beta M} + \frac{2 (1 + \lambda)}{M} \bigg]
\max_{ (t-2M)_+ \leq q \leq t } {\cal E}_c(q) \\
& \hspace{2.25cm} + \frac{ 2 \gamma \overline{A} (M+1) }{\beta M}
\max_{ (t-2M)_+ \leq q \leq t } \bigg( \overline{A}~\| \bar{\prm}(q) - \prm^\star\|  + \frac{ \overline{C} }{N} \sum_{i=1}^N \| {\bm w}_i^q - {\bm w}_i^\star \| \bigg) \eqs.
\end{split}
\eeq
To bound the last term on the right-hand side of \eqref{eq:final_bound_Eg2},

For all $q$, we observe that:
\beq \notag
\begin{split}
& \bigg( \overline{A}~\| \bar{\prm}(q) - \prm^\star\|  + \frac{ \overline{C} }{N} \sum_{i=1}^N \| {\bm w}_i^q - {\bm w}_i^\star \| \bigg)^2 \\
&  \qquad \leq (N+1) (\overline{A})^2 \bigg[  \| \bar{\prm}(q) - \prm^\star\|^2 + \beta \Big( \frac{\overline{C}}{\overline{A}} \Big)^2 \frac{1}{ \beta N} \sum_{i=1}^N \| {\bm w}_i^q - {\bm w}_i^\star \|^2 \bigg]\\
& \qquad \leq (N+1) ~\| {\bm U} \| \max \Big\{ (\overline{A})^2, \beta (\overline{C})^2 \Big\}~  \| \underline{\bm v}(q) \|^2 \eqs,
\end{split}
\eeq
which further implies that
\beq\label{eq:eg_fin}
\begin{split}
& {\cal E}_g(t+1) \leq \Big( \lambda + \frac{ \gamma \rho }{M} \Big) ~{\cal E}_g( t) + \Big(
\frac{ 2 \gamma \overline{A}^2 (M+1) \sqrt{N} }{\beta M} + \frac{2 (1 + \lambda)}{M} \Big)
\max_{ (t-2M)_+ \leq q \leq t } {\cal E}_c(q) \\
& \hspace{3.15cm} + \frac{ 2 \gamma \overline{A} \sqrt{N+1} (M+1) }{\beta M} ~\| {\bm U} \|
\max\{ \overline{A}, \sqrt{\beta} \overline{C} \}
\max_{ (t-2M)_+ \leq q \leq t } \| \widehat{\underline{\bm v}}(q) \| \eqs.
\end{split}
\eeq
Finally, combining \eqref{eq:v_1}, \eqref{eq:fin_c2}, \eqref{eq:eg_fin} shows:
\beq \label{eq:fin_sys}
\left(
\begin{array}{c}
\| \widehat{\underline{\bm v}}(t+1) \| \\[.1cm]
{\cal E}_c(t+1) \\[.1cm]
{\cal E}_g(t+1)
\end{array}
\right)
\leq
{\bm Q}
\left(
\begin{array}{c}
\max_{ (t-2M)_+ \leq q \leq t }  \| \widehat{\underline{\bm v}}(q) \| \\[.1cm]
\max_{ (t-2M)_+ \leq q \leq t }  {\cal E}_c(q) \\[.1cm]
\max_{ (t-2M)_+ \leq q \leq t }  {\cal E}_g(q)
\end{array}
\right) \eqs,
\eeq
where
the inequality sign is applied element-wisely,
and ${\bm Q}$ is a non-negative $3 \times 3$ matrix, defined by:
\beq \label{eq:defq}

\left(
\begin{array}{ccc}
	\theta (\gamma) + \gamma^2 \| {\bm U} \| \| {\bm U}^{-1} \| \overline{G} M (  G + 2 \overline{G} M ) & \gamma \sqrt{N} \| {\bm U} \| ( 1 + \gamma \overline{G} M ) ( \rho + \overline{A} \sqrt{\beta N} ) & 0 \\[.1cm]
	0 & \lambda & \gamma \\[.1cm]
	\frac{ 2 \gamma \overline{A} \sqrt{N+1} (M+1) }{\beta M} ~\| {\bm U} \|
\max\{ \overline{A}, \sqrt{\beta}~ \overline{C} \}
 &
	\sqrt{N} \frac{ 2 \gamma \overline{A}^2 (M+1) }{\beta M} + \frac{2 (1 + \lambda)}{M} &
	\lambda + \frac{\gamma \rho}{M}
\end{array}
\right)\eqs,
\eeq
where $  \theta( \gamma ) \eqdef \| {\bm I} - \gamma {\bm \Lambda } \| = \| {\bm I} - \gamma {\bm G} \| $. Note that the upper bounds for  $ \| {\bm U} \|$ and  $  \| {\bm U}^{-1} \|$ are provided in \eqref{eq:eigen_U}.
Furthermore, also note that  the eigenvalues of $\bm G$ are bounded in \eqref{eq:eigen_G}. We could set the stepsize $\gamma$ to be sufficiently small such that
such that $\theta( \gamma ) \eqdef \| {\bm I} - \gamma {\bm G} \| < 1$.

Finally, we apply  Lemmas ~\ref{lem:ineq} and \ref{lem:exist} presented
in Section~\ref{sec:useful} to the recursive inequality in  \eqref{eq:eg_fin}, which
shows that
each of $\| \underline{\bm v}(t) \|$, ${\cal E}_c(t)$, ${\cal E}_g(t)$
converges linearly with $t$. Therefore, we conclude the proof of  Theorem~\ref{thm:main}.

\subsection{Two Useful Lemmas} \label{sec:useful}
In this section, we present two auxiliary lemmas that are used in the proof of Theorem~\ref{thm:main}.  Our first lemma establish the linear convergence of vectors satisfying recursive relations similar to  \eqref{eq:eg_fin}, provided the spectral radius of ${\bm Q}$ is less than one. In addition, the second lemma verifies this condition for ${\bm Q}$ defined in  in \eqref{eq:defq}.
\begin{Lemma} \label{lem:ineq}
Consider a sequence of non-negative vectors $\{ {\bm e}(t) \}_{t \geq 1} \subseteq \RR^n $ whose evolution is characterized by ${\bm e}(t+1)
\leq
{\bm Q}\!~
{\bm e}( [ (t-M+1)_+ , t ] )$
 for all $t \geq 1$ and some fixed integer $M>0$, where ${\bm Q} \in \RR^{n \times n}$ is a matrix whose entries are nonnegative, and we define
\beq \notag
{\bm e}( {\cal S} ) \eqdef
\left( \begin{array}{c}
\max_{ q \in {\cal S} } ~e_1 (q) \\
\vdots \\
\max_{ q \in {\cal S} } ~e_n(q)
\end{array} \right) \in \RR^n \qquad \text{for any  subset}~{\cal S} \subseteq \NN\eqs .
\eeq
Moreover,

if  ${\bm Q} $  irreducible in the sense that there exists an integer $m$ such that the entries of ${\bm Q}^m$ are all positive,  and the spectral radius of ${\bm Q}$, denoted by $\rho(  {\bm Q} )$,  is strictly  less than one, then for any $t\geq 1$, we have
\beq \label{eq:q_result}
{\bm e}(t) \leq \rho({\bm Q})^{\lceil \frac{t-1}{ M} \rceil} C_1 {\bm u}_1 \eqs,
\eeq
where ${\bm u}_1 \in \RR_{++}^n$ is the top right eigenvector of ${\bm Q}$
and $C_1$ is a constant that depends on the initialization.
\end{Lemma}

{\bf Proof}.
We shall prove the lemma using induction. By the Perron-Frobenius
theorem, the eigenvector ${\bm u}_1$ associated with $\rho({\bm Q})$
is unique and is an all-positive vector. Therefore, there exists $C_1$ such that
\beq\label{eq:case00}
{\bm e}(1) \leq C_1\!~ {\bm u}_1 \eqs.
\eeq

Let us first consider the base case with $t=2,...,M+1$, i.e., $\lceil (t-1) / { M} \rceil = 1$.
When $t=2$, by \eqref{eq:case00} we have,
\beq\label{eq:case01}
{\bm e}(2) \leq {\bm Q} {\bm e}(1) \leq C_1\!~ {\bm Q}\!~ {\bm u}_1 = \rho( {\bm Q})\!~ C_1\!~ {\bm u}_1 \eqs,
\eeq
which is valid as ${\bm Q}$, ${\bm e}(1)$, ${\bm u}_1$ are all non-negative.
Furthermore, we observe that ${\bm e}(2) \leq C_1 {\bm u}_1$.
Next when $t = 3$, we have
\beq \notag
{\bm e}(3) \leq {\bm Q} {\bm e}([1,2]) \overset{(a)}{\leq} C_1\!~ {\bm Q}\!~ {\bm u}_1 = \rho( {\bm Q})\!~ C_1\!~ {\bm u}_1 \eqs,
\eeq
where (a) is due to the non-negativity of vectors/matrix and
the fact ${\bm e}(1), {\bm e}(2) \leq C_1 {\bm u}_1$
as shown in \eqref{eq:case01}.
Telescoping using similar steps, one can   show
${\bm e}(t) \leq \rho( {\bm Q} )\!~ C_1\!~ {\bm u}_1$
for any $t=2,...,M+1$.

For the induction step, let us assume that \eqref{eq:q_result}
holds true for any $t$ up to $t= pM + 1$. That is, we assume that the result holds for all $t$ such that $\lceil (t-1) / { M} \rceil \leq p$.  We shall show that it
also holds for any $t = pM+2, ..., (p+1)M + 1$, i.e., $\lceil (t-1) / { M} \rceil = p+ 1$.
Observe that
\beq \label{eq:induction_case00}
{\bm e}(pM+2)  \leq {\bm Q} \!~ {\bm e}( [ (p-1)M + 2, pM+1 ] )
\leq C_1 \!~ \rho( {\bm Q})^p {\bm Q} {\bm u}_1  =  \rho( {\bm Q})^{p+1}\!~ C_1 \!~ {\bm u}_1 \eqs,
\eeq
where we have used the induction hypothesis.  It is clear that \eqref{eq:induction_case00} is equivalent to \eqref{eq:q_result} with $t = pM+2$.

Similar upper bound can be obtained for ${\bm e}(pM+3)$ as well.
Repeating the same steps,
we show that \eqref{eq:q_result} is true for
any $t = pM+2, ..., (p+1)M + 1$.
Therefore, we conclude the proof of this lemma.

\hfill \textbf{Q.E.D.}\vspace{.2cm}

The following Lemma shows that ${\bm Q}$ defined  in \eqref{eq:defq} satisfies the conditions required in the previous lemma.  Combining these two lemmas yields the final step of the proof of Theorem \ref{thm:main}.
\begin{Lemma} \label{lem:exist}
Consider the matrix ${\bm Q}$ defined in \eqref{eq:defq}, it can be shown that (a) ${\bm Q}$ is an irreducible matrix in $\RR^{3 \times 3} $; (b) there exists a sufficiently
small $\gamma$ such that $\rho( {\bm Q}) < 1$; and (c) as $N,M \gg 1$ and
the graph is geometric, we can set $\gamma = {\cal O}( 1 / \max\{N^2,M^2\})$
and $\rho( {\bm Q}) \leq 1 - {\cal O}( 1 / \max\{N^2,M^2\})$.
\end{Lemma}

{\bf Proof.} Our proof is divided into three parts. The first part shows
the straightforward irreducibility of ${\bm Q}$; the second part
gives an upper bound to the spectral radius of ${\bm Q}$; and
the last part derives an asymptotic bound on $\rho ( {\bm Q})$ when
$N,M \gg 1$.

\paragraph{Irreducibility of ${\bm Q}$}To see that ${\bm Q}$ is irreducible, notice that ${\bm Q}^2 $ is a positive matrix, which could be verified by direct computation.

\paragraph{Spectral Radius of ${\bm Q}$}
In the sequel, we compute an upper bound
to the spectral radius of ${\bm Q}$, and show that if $\gamma$
is sufficiently small, then its spectral radius will be strictly less than one.
First we note that $\theta(\gamma) = 1 - \gamma \alpha$ for some $\alpha > 0$ and the network connectivity satisfies $\lambda<1$.
Also note that $\rho>0$.
For notational simplicity let us define the following
\begin{align*}
& a_1  = \| {\bm U} \| \| {\bm U}^{-1} \| \overline{G} M (  G + 2 \overline{G} M ), ~
a_2 =  \|{\bm U}\| \sqrt{N} ( \rho + \overline{A} \sqrt{\beta N} ), ~ a_3 = \overline{G} M \|{\bm U}\| \sqrt{N} ( \rho + \overline{A} \sqrt{\beta N} ) \nonumber\\
& a_4 = \frac{ 2 \overline{A} \sqrt{N+1} (M+1) }{\beta M}~\| {\bm U} \|
\max\{ \overline{A}, \sqrt{\beta} \overline{C} \}
, \quad   a_5 =	\frac{ 2 \overline{A}^2 (M+1) \sqrt{N} }{\beta M}, \quad a_6 = \frac{2(1+ \lambda)}{M}.
\end{align*}
With the above shorthand definitions,
the characteristic polynomial for ${\bm Q}$, denoted by $g\colon \RR\rightarrow \RR$,  is given by
\begin{align*}
g(\sigma)& = \mbox{det}\left(
\begin{array}{ccc}
\sigma - (1- \gamma \alpha + \gamma^2 a_1) & -\gamma a_2 - \gamma^2 a_3 & 0 \\[.1cm]
0 & \sigma-\lambda & -\gamma \\[.1cm]

- \gamma a_4 &

-\gamma a_5 - a_6 &
\sigma - \Big( \lambda + \frac{\gamma \rho}{M} \Big)
\end{array}
\right).
\end{align*}
By direct computation, we have
\beq
\begin{split}
g(\sigma) & = (\sigma - (1-\gamma \alpha + \gamma^2 a_1 ) ) \!~ g_0(\sigma) - \gamma^3 ( a_2 + \gamma a_3 ) a_4
\end{split}
\eeq
where
\beq
g_0(\sigma) \eqdef (\sigma - \lambda)^2 - \frac{\gamma \rho}{M} (\sigma-\lambda) - \gamma( \gamma a_5 + a_6) \eqs.
\eeq
Notice that the two roots of the above polynomial can be upper bounded by:
\beq
\lambda + \frac{\gamma \rho}{2M} \pm \biggl[ \bigg( \frac{\gamma \rho \sqrt{N}}{2M} \bigg)^2  + \gamma ( \gamma a_5 + a_6 ) \biggr ] ^{1/2} \leq \overline{\sigma} \eqdef \lambda + \frac{\gamma \rho}{M} + \sqrt{ \gamma( \gamma a_5 + a_6 ) }
\eeq
In particular, for all $\sigma \geq \overline{\sigma}$, we have
\beq
g_0( \sigma) \geq ( \sigma - \overline{\sigma}  )^2 \eqs.
\eeq

Now, let us define
\beq \label{eq:sig_upperbd}
\sigma^\star \eqdef \max \left\{ \frac{\gamma \alpha}{4} + 1 - \gamma \alpha + \gamma^2 a_1, \overline{\sigma} + \gamma \sqrt{\frac{4 (a_2 + \gamma a_3) a_4}{\alpha}} \right\}
\eeq
Observe that for all $\sigma \geq \sigma^\star$, it holds that
\beq
\begin{split}
g(\sigma) & \geq (\sigma - (1- \gamma \alpha + \gamma^2 a_1) ) ( \sigma - \overline{\sigma} )^2 - \gamma^3 ( a_2 + \gamma a_3 ) a_4 \\
& \geq \frac{\gamma \alpha}{4} \!~ \gamma^2 \frac{4 ( a_2 + \gamma a_3) a_4}{\alpha} - \gamma^3 ( a_2 + \gamma a_3 ) a_4 = 0\eqs.
\end{split}
\eeq
Lastly, observe that $g(\sigma)$ is strictly increasing for all
$\sigma \geq \sigma^\star$. Combining
with the Perron Frobenius theorem shows that
$\rho( {\bm Q} ) \leq \sigma^\star$.
Moreover, as $\lambda < 1$ and $\alpha > 0$, there
exists a sufficiently small $\gamma$ such that $\sigma^\star < 1$.
We conclude that $\rho ( {\bm Q} ) < 1$ in the latter case.

\paragraph{Asymptotic Rate when $M , N \gg 1$}
We evaluate a sufficient condition on $\gamma$ for the
proposed algorithm to converge, \ie when $\sigma^\star < 1$.
Let us consider \eqref{eq:sig_upperbd} and the
first operand in the $\max\{ \cdot\}$. The first operand is guaranteed to
be less than one if:
\beq \label{eq:sig_1}
\gamma \leq \frac{\alpha}{2 a_1} \Longrightarrow
\frac{\gamma \alpha}{4} + 1 - \gamma \alpha + \gamma^2 a_1 \leq 1 - \frac{\gamma \alpha}{4} \eqs.
\eeq
Moreover, from the definition of $a_1$, we note that this requires $\gamma = {\cal O}(1/M^2)$ if $M \gg 1$.

Next, we notice that for geometric
graphs, we have $\lambda = 1 - c/N$ for some positive $c$. Substituting this
into the second operand in
\eqref{eq:sig_upperbd} gives
\beq \label{eq:sig_2}
1 - \frac{c}{N} + \frac{\gamma \rho}{M} + \sqrt{ \gamma( \gamma a_5 + a_6 ) }
+  \gamma \sqrt{\frac{4 (a_2 + \gamma a_3) a_4}{\alpha}} < 1 \eqs.
\eeq
Therefore, \eqref{eq:sig_1} and \eqref{eq:sig_2} together give a sufficient
condition
for $\sigma^\star < 1$.

To obtain an asymptotic rate
when $M , N \gg 1$.
Observe that $a_2 = \Theta( {N})$, $a_3 = \Theta(  {N} M)$, $a_4 = \Theta(\sqrt{N})$,
$a_5 = \Theta(\sqrt{N})$, $a_6 = \Theta(1/M)$.
Moreover, the condition \eqref{eq:sig_1} gives $\gamma = {\cal O}(1/M^2)$, therefore the left hand side of Eq.~\eqref{eq:sig_2} can be approximated by
\beq
1 - \frac{c}{N} +
\gamma \!~ \Theta \left( {N}^{\frac{3}{4}} \right)
+ \sqrt{\gamma} \!~ \Theta ( 1 / \sqrt{M} ) \eqs .

\eeq
Setting the above to $1 - c/(2N)$ requires one to have $\gamma = {\cal O}(1/N^{2})$.

Finally, the above discussions show that
setting $\gamma = {\cal O}( 1 / \max\{N^{2},M^2\})$ guarantees
that $\sigma^\star < 1$. In particular, we have
$\sigma^\star \leq \max\{ 1 - \gamma \frac{\alpha}{4}, 1 - c/(2N) \} = 1 - {\cal O}( 1 / \max\{ N^{2}, M^2 \})$.
\hfill \textbf{Q.E.D.}

\subsection{Derivation of  Equation (\ref{eq:new_equality})} \label{sec:detailed}
We  we establish  \eqref{eq:new_equality} with details. Recall that $\underline{\bm h}(t) $ and $\underline{\bm v}(t) $ are defined in \eqref{eq:define_3vectors}. We verify this equation for each block of  $\underline{\bm h}(t) $.
To begin with, for the first block, for ${\bm h}_{\prm} (t)$ defined in \eqref{eq:4terms_1}, we have
\beq \notag
{\bm h}_{\prm} (t) = \rho \bar{\prm}(t) + \frac{1}{N} \sum_{i=1}^N \hat{\bm A}^\top {\bm w}_i^t
 = \rho \big( \bar{\prm}(t) - \prm^\star + \prm^\star \big) + \frac{1}{N} \sum_{i=1}^N \hat{\bm A}^\top {\bm w}_i^t \eqs.
\eeq
Recall from \eqref{eq:opt_cond} that
$\rho \prm^\star = - \frac{1}{N} \sum_{i=1}^N \hat{\bm A}^\top {\bm w}_i^\star$,
which implies that
\beq \label{eq:fin_eq_1}
{\bm h}_{\prm} (t)
= \rho \big( \bar{\prm}(t) - \prm^\star \big) + \sum_{i=1}^N \sqrt{\frac{\beta}{N}} \hat{\bm A}^\top \!~ \frac{1}{\sqrt{\beta N}} \big( {\bm w}_i^t - {\bm w}_i^\star \big)
= [  {\bm G} \underline{\bm v}(t)  ] _{1}  \eqs,
\eeq
where $ [  {\bm G} \underline{\bm v}(t)  ] _{1} $ denotes the first block of $    {\bm G} \underline{\bm v}(t)  $.

It remains to establish the equation for the remaining blocks. For any $i \in \{ 1, \ldots, N\}$, let us focus on the $i+1$-th block. By the definition of ${\bm h}_{\bm w_i}(t)$ in \eqref{eq:4terms_2}, we have
\beq\notag
- \sqrt{\frac{\beta}{N}}  {\bm h}_{\bm w_i}(t) =
- \sqrt{\frac{\beta}{N}} \big( \hat{\bm A} \bar{\prm}(t) - \hat{\bm C} {\bm w}_i^t - \hat{\bm b}_i \big)
= - \sqrt{\frac{\beta}{N}} \big( \hat{\bm A} ( \bar{\prm}(t) - \prm^\star ) + \hat{\bm A} \prm^\star - \hat{\bm C} {\bm w}_i^t - \hat{\bm b}_i \big) \eqs.
\eeq
Again from \eqref{eq:opt_cond}, it holds  that $\hat{\bm A} \prm^\star
= {\bm b}_i + \hat{\bm C} {\bm w}_i^\star$. Therefore,
\beq \label{eq:fin_eq_i}
- \sqrt{\frac{\beta}{N}} \big( \hat{\bm A} \bar{\prm}(t) - \hat{\bm C} {\bm w}_i^t - \hat{\bm b}_i \big)
= - \sqrt{\frac{\beta}{N}} \hat{\bm A} ( \bar{\prm}(t) - \prm^\star )
+ \beta \hat{\bm C} \!~ \frac{{\bm w}_i^t - {\bm w}_i^\star}{\sqrt{\beta N}}
=[  {\bm G} \underline{\bm v}(t)  ]_{i+1}\eqs,
\eeq
where $[  {\bm G} \underline{\bm v}(t)  ]_{i+1}$ denotes the $i+1$-th  block of $ {\bm G} \underline{\bm v}(t)$.
Combining \eqref{eq:fin_eq_1} and \eqref{eq:fin_eq_i} gives
the desired equality.

\section{Additional Experiments}
An interesting observation from Theorem~\ref{thm:main}
is that the convergence rate of {\sf PD-DistIAG}
depends on $M$ and the topology of the graph.
The following experiments will demonstrate the effects of these on the algorithm,
along with the effects of regularization parameter $\rho$.
\begin{figure}[H]
\centering
\includegraphics[width=.425\linewidth]{./Fig/pcrit.eps}~
\includegraphics[width=.425\linewidth]{./Fig/ring.eps}
\caption{Illustrating the graph topologies in the additional experiments. (Left) ER graph with connectivity probability of $1.01\log N / N$. (Right) Ring graph.} \label{fig:graph2}
\end{figure}

\begin{figure}[H]
\centering
\includegraphics[width=.425\linewidth]{./Fig/Revise_N500d300M500_rho1e-2.eps}~
\includegraphics[width=.425\linewidth]{./Fig/Revise_N500d300M500_rho1e-1.eps}
\caption{Experiment with \texttt{mountaincar} dataset. For this problem, we
only have  $d=300$, $M=500$ samples, but yet there are $N=500$ agents.
(Left) We set $\rho = 0.01$. (Right) We set $\rho = 0.1$.} \label{fig:two}
\end{figure}

To demonstrate the dependence of {\sf PD-DistIAG} on the graph topology,
we fix the number of agents at $N=500$ and compare the performances
on the ring and the
ER graph set with probability of connection of $p= 1.01 \log N / N$, as illustrated
in Fig.~\ref{fig:graph2}.
Notice that the ring graph is not a geometric graph and its connectivity parameter,
defined as $\lambda \eqdef \lambda_{\sf max} ( {\bm W} - (1/N) {\bf 1}{\bf 1}^\top )$
from the previous section can be much closer to $1$ than the ER graph.
Therefore, we expect the {\sf PD-DistIAG} algorithm to converge slower
on the ring graph. This is corroborated by Fig.~\ref{fig:two}.
Furthermore, from the figure, we observe that with a larger regularization
$\rho$, the disadvantage for using the ring graph has exacerbated.
We suspect that this is due to the fact that the convergence speed is limited
by the graph connectivity, as seen in \eqref{eq:defq};
while in the case of ER graph, the algorithm
is able to exploit the improved problem's condition number.

Next, we consider the same set of experiment but increase the number of samples
to $M=5000$.
\begin{figure}[htpb]
\centering
\includegraphics[width=.425\linewidth]{./Fig/Revise_N500d300M5000_rho1e-2.eps}~
\includegraphics[width=.425\linewidth]{./Fig/Revise_N500d300M5000_rho1e-1.eps}
\caption{Experiment with \texttt{mountaincar} dataset. For this problem, we
 have  $d=300$, $M=5000$ samples, but yet there are $N=500$ agents.
(Left) We set $\rho = 0.01$. (Right) We set $\rho = 0.1$.} \label{fig:three}
\end{figure}

Interestingly, for this example, the performances
of the ring graph and the ER graph settings are almost identical in this setting
with large sample size $M$.
This is possible as we
recall from Theorem~\ref{thm:main} that
the algorithm converges at a rate of ${\cal O}(\sigma^t)$ where
$\sigma = 1 - {\cal O}( 1 / \max\{ MN^2, M^3 \})$. As we have $M \gg N$,
the impact from the sample size $M$ becomes dominant, and is thus
insensitive to the graph's connectivity.

config: arxiv


TITLE: Upper bounds on the length of longest simple path in non-Hamiltonian graph?
QUESTION [8 upvotes]: Hamiltonian cycle problem is $NP$-complete on cubic planar bipartite graphs. I'm interested in upper bounds on the length of the longest simple path in non-Hamiltonian cubic planar bipartite graphs.

What is the best known upper bound on the length of longest simple path in non-Hamiltonian cubic planar bipartite graphs?

Edit: Also, I am interested in non-trivial lower bounds on the length of the longest simple path in this class of graphs.

REPLY [2 votes]: Questions of this kind are especially interesting for graphs which are 3-polytopal (edge-vertex graphs of 3-dimensional convex polytopes) and for the case of the graph being bipartite. (Also for higher-dimensional polytopes.)
The concept of "shortness exponent" has emerged to measure how short a longest cycle might be in a graph which has no hamiltonian circuit and which is within a family of graphs.
This relatively recent paper lists many references but others can be found using the string: shortness exponent polytopes:
http://dml.cz/dmlcz/129289


TITLE: Exponents in the denominator?
QUESTION [2 upvotes]: I'm having trouble understanding exponents in the denominator.
For example: I have the expression: $\displaystyle 1 - \frac{1}{3^n} + \frac{2}{3^{n+1}}$.
I know that this simplifies to $\displaystyle 1 - \frac{1}{3^{n+1}}$, but how/why? Can someone please list the steps?
My understanding is that the exponent $(n+1)$ in the expression $x^{n+1}$ means that $x^{n+1} = x x^n$, but how does this fit with the above problem?

REPLY [2 votes]: My understanding is that the exponent $n+1$ means that $x^{n+1}=x\cdot x^n$

Your understanding is correct, and you can apply it to the problem at hand by remembering that when an exponent, say $n$, of an expression is in the denominator of a fraction, it can be written as an expression raised to the $-n$ power. Then you can manipulate exponents by the respective rules to which you are accustomed.  $$\frac{1}{x^{n+1}} = x^{-(n+1)} = x^{-n-1} = x^{-1}x^{-n} = \frac {1}{x\cdot x^n} < \frac{1}{x^n} = x^{-n}$$(Note: the inequality holds, as stated, provided $ n > 1$.)
That is, so we have that the "least common denominator" is $x\cdot x^n$, with $$\frac{1}{x^n} = x^{-n} = x^1\cdot x^{-n - 1} = \frac{x}{x\cdot x^n} = \frac {x}{x^{n+1}}$$
In your problem, then $$1-\frac{1}{3^n}+\frac{2}{3^{n+1}} = 1 - 3^{-n} + 2\cdot 3^{-(n+1)} = 1 - 3\cdot 3^{-n - 1} + 2\cdot 3^{-n - 1} $$ $$= 1 + (-3 + 2)\cdot 3^{-n-1} = 1 - 3^{-(n+1)} = 1 - \frac{1}{3^{n+1}}$$


TITLE: Using Wolfram Alpha to solve a system of linear equations
QUESTION [3 upvotes]: How do I input the below system of equations in Wolfram Alpha in order to solve for the unknowns?
I'm wondering if there's some kind of code that can be written in order to make wolfram alpha understand what I'm talking about.
$$\left.\begin{matrix}
 a+b+c+d+e = 0\\
(-a+c+2d+3e) h = 1\\
 (a+c+4d+9e)\frac{h^2}{2}= 0\\
(-a+c+8d+27e)\frac{h^3}{6}=0\\
(a+c+16d+81e)\frac{h^4}{24}=0\\
 \end{matrix}\right\}$$
I've tried many things already, like
solve{a+b+c+d+f=0, (-a+c+2d+3f)h=1, (a+c+4d+9f)h^2/2=0,
(-a+c+8d+27f)h^3/6=0, (a+c+16d+81f)h^4/24=0,[a,b,c,d,e]}

Thanks for any help.

REPLY [0 votes]: You have 6 variables but only 5 equations, so there should be a free variable. Mathematica did this just fine for me. What I entered was
Solve[
 a + b + c + d + e == 0 && (-a + c + 2 d + 3 e) h ==
   1 && (a + c + 4 d + 9 e) h^2/2 ==
   0 && (-a + c + 8 d + 27 e) h^3/6 ==
   0 && (a + c + 16 d + 81 e) h^4/24 == 0, {a, b, c, d, e, h}]
which gave me the solution
$$a =\frac{-1}{4h},b=\frac{-5}{6h},c=\frac{3}{2h}d=\frac{-1}{2h},e=\frac{1}{12h}$$
with a simple warning. I believe it was just the syntax of how you entered it. Mathematica is a useful tool but is very picky. Their help function always has useful examples and a good place when you have trouble is to start by seeing how they demonstrate approaching things.


TITLE: Does every bounded sublattice of a bounded lattice have the same top and bottom?
QUESTION [1 upvotes]: Question: Given a bounded lattice $\mathscr{L}$ with top $T$ and bottom $B$, is it the case that any sublattice of $\mathscr{M} \subseteq \mathscr{L}$ which is bounded must also have $T$ as its top and $B$ as its bottom?
Or could other elements from $\mathscr{L}$, some $T'$ and $B'$, assume the role of the top and bottom of $\mathscr{M}$?

I think the answer to the latter question is no, but I am not sure if my idea for the proof is actually correct given the definitions of lattice and bounded lattice, which I am not sure I fully understand.
Note: This is a follow-up to a previous question.
Attempt: By definition or something else, because $\mathscr{L}$ is bounded, the empty join must be $B$ and the empty meet must be $T$. Any meet operation which has a different empty meet would be a different/non-equal meet operation. Any join operation which has a different empty join would be a different/non-equal join operation. (Because this would imply that they were defined differently.)
Thus, if the bottom of $\mathscr{M}$ were $B' \not=B$, then that could only be the case if the join operation on $\mathscr{M}$ were different from the join operation on $\mathscr{L}$. Thus the ground set of $\mathscr{M}$ may be a subset of the ground set of $\mathscr{L}$, but since the join operations are different, $\mathscr{M}$ is not a sublattice of $\mathscr{L}$.
Likewise, if the top of $\mathscr{M}$ were $T' \not=T$, then that could only be the case if the meet operation on $\mathscr{M}$ were different from the meet operation on $\mathscr{L}$. Thus even though the ground set of $\mathscr{M}$ is a subset of the ground set of $\mathscr{L}$, and both are posets with respect to the same partial order, their meet operations must necessarily be different, and therefore $\mathscr{M}$ cannot be a sublattice of $\mathscr{L}$.

REPLY [1 votes]: This depends on what you mean with bounded lattice.
If you mean a lattice $\mathbf{L} = \langle L, \wedge, \vee \rangle$ which just happens to be bounded (meaning that it has a maximum and a minimum element), then a sublattice $\mathbf{M}$ of $\mathbf{L}$ doesn't even have to be bounded, but even a bounded lattice doesn't have to have the same bounds.
For example, each element of a lattice is a sublattice coinciding with its minimum and maximum.
If by a bounded lattice you mean $\mathbf{L} = \langle L, \wedge, \vee, 0, 1 \rangle$ (here the bounds are nullary operations), then every bounded sublattice of $\mathbf{L}$ must have the same $0$ and $1$ (precisely because these are fundamental operations of the algebra).
So this is essentially a matter of definition.

By the way, in your argument, you seem to be considering that if $\mathbf{L}$ is a bounded lattice and $\mathbf{M}$ a bounded sublattice of $\mathbf{L}$, then for any $B \subseteq M$, we have $\bigwedge_{M} B = \bigwedge_L B$.
This is not the case.
For example, consider the usual order on the set
$$L = \{ -1, 0 \} \cup \{ 1/n : n \in \mathbb{N} \}.$$
This is a bounded lattice with $\top = 1$ and $\bot = -1$.
Now consider $M = L \setminus \{0\}$; it is a bounded sublattice of $L$, but, taking $B = L \setminus \{-1,0\}$ we have
$\bigwedge_M B = -1 \neq 0 = \bigwedge_L B.$


TITLE: Proving $\arctan(\mathrm{e}^{-v}) = \text{arccot}(\mathrm{e}^v)$
QUESTION [3 upvotes]: Is this a correct way to prove that
$$ \arctan(\mathrm{e}^{-v}) = \text{arccot}(\mathrm{e}^v) $$
$$\tan x = \frac{1}{\mathrm{e}^v} $$
Turn $\tan x$ into $\sin x$ and $\cos x$
$$\frac{\sin x}{\cos x} =  \frac{1}{\mathrm{e}^v}$$
Multiply $\cos x$
$$ \sin x = \frac{\cos x}{\mathrm{e}^v} $$
$$ \mathrm{e}^v \sin x = \cos x$$
$$ \mathrm{e}^v = \frac{\cos x}{\sin x}$$
Multiply by $\mathrm{e}^v$ and divide by $\sin x$
$$ \mathrm{e}^v = \cot x$$
$$\text{arccot}(\mathrm{e}^v) = x$$

REPLY [0 votes]: Yes but a simpler way to do it is to set everything equal to one another
$$\arctan(x)=\frac{1}{e^v} \iff e^v=\mathrm{arccot}(x)$$
$$\frac{\arcsin(x)}{\arccos(x)}=\frac{1}{e^v}\iff e^v=\frac{\arccos(x)}{\arcsin(x)}$$
everything cancels out resulting in that they do equal each other in the set $\{v : v \in \mathbb R\}$ because $\frac{1}{e^v}$ or $e^v$ does not equal zero ever.

REPLY [0 votes]: Hint: You may also use the mean value theorem. Let $f(x)=\arctan (e^x)-\arctan (e^{-x})$, so $f'(x)=\displaystyle \frac{e^x}{1+e^{2x}}-\frac{e^{-x}}{1+e^{-2x}}\Longrightarrow f'(x)=\displaystyle \frac{e^x}{1+e^{2x}}-\frac{e^{x}}{1+e^{2x}}=0\Longrightarrow f(x)=$constant by the mean value theorem. If you put $x=0$ you get constant$=0$.


TITLE: Subring and idempotent elements
QUESTION [1 upvotes]: Given ring $(S,+,*)$ and $S=\{(x,y)\in \mathbb{Z} \times \mathbb{Z} \mid x\equiv y  \pmod 2\}$, where $\mathbb{Z}$ is the set of integers. Find all idempotent elements of $S$.

How to approach this? I'm not even sure how to multiply ordered pairs. Basically I have to find x for which $(x,x)*(x,x)=(x,x)$, correct?
My attempt was $(x^2, x^2) = (x,x)$ thus $x^2 = x$ and $x=0$ or $x=1$.
And elements are $(1,1)$ and $(0,0)$.

REPLY [1 votes]: An idempotent in a subring is also such in the bigger ring.
The idempotents in the ring $\mathbb{Z}\times\mathbb{Z}$ are the elements $(x,y)$ such that
$$
(x,y)=(x,y)^2=(x^2,y^2)
$$
so $x=0$ or $x=1$ and $y=0$ or $y=1$. These four elements are indeed idempotents; but only two belong to the subring $S$ which consists of the elements $(x,y)$ where $x$ and $y$ are either both even or both odd.


TITLE: Asymptotic behaviour of of $\sum_{n=0}^k a_n b_{k-n}$
QUESTION [2 upvotes]: Let $(a_n)_n$ and $(b_n)_n$ be two sequences of positive numbers such that:
-$a_n\sim a/n^{3/2}$ for some $a>0$;
-$b_n\sim b/n^{3/2}$ for some $b>0$;
Is it true that as $k\to \infty$,
$\sum_{n=0}^k a_n b_{k-n}\sim \frac{1}{k^{3/2}}(a\sum_{n=0}^{\infty}b_n+b\sum_{n=0}^{\infty}a_n) ?$
If not true, under what additional conditions the statement is true?

REPLY [1 votes]: It's true that:  $\ \displaystyle \sum_{k=0}^n a_k b_{n-k}\sim \frac{1}{n^{3/2}}(a\sum_{k=0}^{\infty}b_k+b\sum_{k=0}^{\infty}a_k) $
Here is a demonstration.
$\displaystyle \sum_{k=0}^na_kb_{n-k} =t_n+u_n+v_n+w_n \quad $ with:
$t_n=\displaystyle \sum_{k=0}^{\lfloor \root{3}\of{n}\rfloor}a_kb_{n-k}   \quad  , \quad u_n= \displaystyle \sum_{k=\lfloor \root{3}\of{n}\rfloor+1}^{\lfloor n/2\rfloor }a_kb_{n-k} \quad ,\quad v_n = \sum_{k=\lfloor n/2\rfloor +1}^{n-\lfloor \root{3}\of{n}\rfloor} a_kb_{n-k} \quad ,\quad w_n=\sum_{k=n-\lfloor \root{3}\of{n}\rfloor +1}^n a_kb_{n-k}$

We know that there exists B such that $\ \forall n\geqslant 1 \ , \ b_n\leqslant \dfrac{B}{n^{3/2}}   $. Then $ \ \displaystyle u_n\leqslant \sum_{k= \lfloor \root{3}\of{n}\rfloor+1}^{\lfloor n/2\rfloor }  a_k \dfrac{B}{(n-\lfloor n/2\rfloor)^{3/2}}   $.
$\displaystyle 0\leqslant u_n\leqslant 2^{3/2}B \sum_{k=\lfloor \root{3}\of{n}\rfloor+1}^{+\infty}a_k \dfrac{1}{n^{3/2}} \quad $. So $\ u_n={\rm o}\left( \dfrac{1}{n^{3/2}}\right)$
By the same idea  $\ v_n={\rm o}\left( \dfrac{1}{n^{3/2}}\right)$

$t_n-\displaystyle \dfrac{b}{n^{3/2}}\sum_{k=0}^{+\infty}a_k = x_n+y_n+z_n\quad   $ with
$x_n=\displaystyle \sum_{k=0}^{\lfloor \root{3}\of{n}\rfloor} a_kb \left(\dfrac{1}{(n-k)^{3/2}}-\dfrac{1}{n^{3/2}} \right)  , \quad y_n= \sum_{k=0}^{\lfloor \root{3}\of{n}\rfloor} a_k\left(b_{n-k}- \dfrac{b}{(n-k)^{3/2}}\right), \quad   z_n=-\dfrac{b}{n^{3/2}}\sum_{k=\lfloor \root{3}\of{n} \rfloor +1}^{+\infty} a_k $

It's clear that $\ z_n={\rm o}\left(\dfrac{1}{n^{3/2}}\right)$
$\displaystyle 0\leqslant x_n\leqslant \sum_{k=0}^{\lfloor \root{3}\of{n}\rfloor} a_kb \left(\dfrac{1}{(n-\lfloor \root{3}\of{n}\rfloor)^{3/2}}-\dfrac{1}{n^{3/2}} \right) \leqslant \dfrac{1}{n^{3/2}} \sum_{k=0}^{+\infty}a_kb \left( \dfrac{1}{\left( 1- \frac{\lfloor \root{3}\of{n}\rfloor }{n}\right)^{3/2}}-1\right)\ $. So  $\ x_n={\rm o}\left( \dfrac{1}{n^{3/2}}\right)$
$|y_n| \leqslant \displaystyle \sum_{k=0}^{\lfloor \root{3}\of{n}\rfloor} \dfrac{a_k}{(n-k)^{3/2}} \left| (n-k)^{3/2}b_{n-k}-b\right| \leqslant \dfrac{1}{(n-\root{3}\of{n})^{3/2}}\sum_{k=0}^{+\infty}a_k \sup_{p\geqslant n-\lfloor \root{3}\of{n}\rfloor} |p^{3/2}b_p-b|\ $ .
And  $\ y_n={\rm o}\left( \dfrac{1}{n^{3/2}}\right)$

So, we have  $\ t_n \sim \dfrac{1}{n^{3/2}} b\displaystyle\sum_{k=0}^{+\infty} a_k$
With the same ideas $\ w_n \sim \dfrac{1}{n^{3/2}} a\displaystyle\sum_{k=0}^{+\infty} b_k$
And we can conclude (we may add the equivalents because they are positive).


TITLE: Meaning of $\mathbb{R}[x]$
QUESTION [6 upvotes]: I ran into this expression in a paper I was reading, and I'm confused about part of the meaning.  Here $u$ and $v$ are two polynomials.
$$u, v \in \mathbb{R}[x]$$
I'm not really familiar with usage of $[x]$ here, but if it means "nearest integer", then isn't this expression equivalent to simply:
$$u, v \in \mathbb{Z}$$

REPLY [5 votes]: Generally, if $\rm\,R \subset S\,$ are rings and $\rm\,s\in S\,$ then $\rm\,R[s]\,$ denotes the ring-adjunction of $\rm\,s\,$ to $\rm\,R,\,$ i.e. the smallest subring of $\rm\,S\,$ containing both $\rm\,R\,$ and $\rm\,s\,.\,$ Equivalently $\,\rm R[s]$ is the image of $\rm\,R[x]\,$ under the evaluation map $\rm\,x\mapsto s,\,$ i.e.  elements of $\rm\,S\,$ writable as a polynomial in $\rm\,s\,$ with coefficents in $\rm\,R.\,$
Similarly, if $\rm\,F \subset E\,$ are fields and $\rm\,\alpha\in E\,$ then $\rm\,F(e)\,$ denotes the field-adjunction of $\rm\,\alpha\,$ to $\rm\,F,\,$ i.e. the smallest subfield of $\rm\,E\,$ containing both $\rm\,F\,$ and $\rm\,\alpha.$
The notation for the polynomial ring $\rm\,R[x]\,$ is  the special case where $\rm\,x\,$ is transcendental over $\rm\,R\ $ (an "indeterminate" in old-fashioned language),$\ $ i.e. $\rm\, x\,$ is not a root of any polynomial with coefficients in $\rm\,R\,$. One may view $\rm\,R[x]\,$ as the most general ring obtained by adjoining a universal (generic) element $\rm\,x,\,$ in the sense that any other adjunction $\rm\,R[s]\,$ is a ring-image of $\rm\,R[x]\,$ under the evaluation homomomorphism $\rm\, x\to s\,.\ $
For example, if $\rm\,R \subset S\,$  are fields then $\rm\,R[s]\cong R[x]/(f(x))\,$ where $\rm\,f(x)= \,$ minimal polynomial of $\rm\,s\,$ over $\rm\,R.\,$ Essentially this serves to faithfully ring-theoretically model $\rm\,s\,$ as a "generic" root $\rm\,x\,$ of the minimal polynomial $\rm\,f(x)\,$ for $\rm\,s\,.\,$
Polynomial rings may be characterized by the existence and uniqueness of such evaluation maps ("universal mapping property"), e.g. see any textbook on Universal Algebra, e.g. Bergman.


TITLE: Find the inverse of $f(x)= 3x^2 - 3x -11$, where $x>2$
QUESTION [1 upvotes]: Find the inverse of $f(x)= 3x^2 - 3x -11$, where $x > 2$

The answer guide says the answer is $f^{-1}(x)=\frac{1}{2} + \sqrt{ \frac{x}{3}} +\frac{47}{12}$,
but i had $\frac{1}{2} + \sqrt{\frac{x}{3} +\frac{47}{12}}$ instead.
How do i get the correct answer?

REPLY [2 votes]: To find the innverse of $f(x)$, you have to swap $x$ and $y$, obtaining:
$$x=f(y)=3y^2-3y-11=\left(\sqrt{3}y-\frac{\sqrt{3}}{2}\right)^2-11-\frac{3}{4}$$
From here you solve for $y$, having:
$$x+11+\frac{3}{4}=3\left(y-\frac{1}{2}\right)^2$$
And so:
$$\sqrt{\frac{x}{3}+\frac{47}{12}}=y-\frac{1}{2} \leftrightarrow y = \sqrt{\frac{x}{3}+\frac{47}{12}}+\frac{1}{2}$$
Your answer is correct. There is certanly a typing error in the answer given.


TITLE: How many length 10 words can we make that start with "TRY" or end with "TRY"?
QUESTION [2 upvotes]: With replacement and repetition is allowed, if we can choose from the 26 letters of the alphabets, how many length 10 strings/ words can we make that either start with the substring "try" or end with "try". I know this is about the inclusion exclusion principle, so it would be words that start with TRY + words that end with TRY - the duplicates between them. This is how I started it:
Words that start with try: 26^7 (because first 3 letters are not changeable).
Words that end with try: 26^7 (last 3 letters are not changeable)
But how do I calculate the numbers that both begin and end with try (the duplicates) ?
Thanks.

REPLY [0 votes]: There are $N=26^4$ string which both start and end with TRY. The next action depends on the fact if such words are allowed (this is not quite clear from the question).
If they are allowed you should subtract $N$ once, and if not allowed - twice.


TITLE: Does Gödel's theorem rule out derivations from all possible logical systems or just first-order logic?
QUESTION [0 upvotes]: Gödel's first incompleteness theorem excludes the possibility of formulating a consistent and decidable set of first order sentences which are true in standard arithmetic from which the truth/falsehood of every possible first order statement can be derived.
But Peano's axioms include a second order statement. I know that second order logic is incomplete so that we can't derive the truth or falsehood of all second order statements, but since peano's axioms (with the second order induction axiom rather than the first order scheme) characterize arithmetic up to isomorphism, it seems possible that we could derive at least all first order statements using the second order axiom.
My question is essentially about the meaning of Gödel's theorem: does it merely exclude the possibility of using first order logic to derive all first order statements, or does it exclude the possibility of proving the truth/falsehood of all first order statements, no matter what additional extensions we add to the logical system (such as infinite disjunction, second-order formula's, statements about countability, etc)?

EDIT: My question hasn't been answered yet, so let me clarify:
Here is ONE possible way to think about my question:

We cannot have a set of first order axioms for arithmetic from which all first order sentences can be proven or disproven (first incompletness theorem)
We cannot prove for all second order sentences all their second order implications. (incompleteness of second order logic)
But can we have a set of second order axioms for arithmetic, from which we can prove or disprove all first-order sentences? (or is this ruled out by godel's theorem as well?)

REPLY [4 votes]: The initial claim

Gödel's first incompleteness theorem excludes the possibility of formulating a consistent and decidable set of first order sentences from which the truth/falsehood of every possible first order statement can be derived.

is just wrong. There are lots of complete first-order theories -- i.e. theories which determine the truth/falsity of every closed wff expressible in the language of the theory. (And of course, you don't need Gödel to tell you that a theory in one language won't settle the truth values of sentences from another language!). For example Tarski's axioms for geometry, the first-order theory of real closed fields, etc.
So, as a first step in getting yourself clear, find out what Gödel actually showed. For example, here are some lecture notes, Gödel Without Tears.


TITLE: How can the intersection of nonzero ideals be zero?
QUESTION [3 upvotes]: In Artin, exercise 6.8 of chapter 11, in part c he mentions ideals $I,J$ such that $I\cap J=0$. But if $I$ and $J$ are nonzero, then if $i\in I,j\in J$, then $ij\in I $ and $ij\in J$, right? So don't all ideals share nonzero elements?
On second thought, I guess $ij$ could be zero for all $i$ and $j$. Is this the only exception?

REPLY [0 votes]: This is more of a long comment.
It is interesting to consider the connections between intersection and product of ideals; see this MO topic.
It is common to require that ideals be non-degenerate in some sense, e.g. "$s$-unital": for every $x\in I$, there is $u\in I$ such that $xu=x$. In case that both $I$ and $J$ are $s$-unital, we have $I\cap J$ the set of products $ij$ where $(i,j)\in I\times J$. This property (or approximated versions) are true in several examples, e.g. closed ideals of C*-algebras, and these are usually not domains.
Here is a nice example: if $R$ is any domain and $X$ is any set (nonempty, not a singleton), consider the ring $A=\oplus_X R$ of finitely supported functions from $X$ to $R$. The $s$-unital ideals of $A$ are precisely those of the form $A_Y=\left\{(r_x)_{x\in X}:r_x=0\text{ whenever }x\not\in Y\right\}$ for subsets $Y\subseteq X$ (this is a discrete version of the Gelfan-Kolmogorov Theorem). Neither $A$ nor any of these ideals $A_Y$ are domains, but they are all $s$-unital. In this case $A_Y\cap A_Z=A_{Y\cap Z}$.


TITLE: Quadratic equation that takes 2 zeroes and keeps the vertex at y = 10
QUESTION [0 upvotes]: I'm not the best at algebra so I will try to word this in the best way I can.
Let's say I have 2 solutions in each of 2 solution sets:
Set 1: (6, 0) and (18, 0) (visual here)
Set 2: (0, 0) and (2, 0) (visual here)
As you can see, the y position of the vertices for both of the equations shown above are different (set 1's vertex has a y position of about -36 and set 2's vertex has a y position of about -1)
How would I go about writing a quadratic equation that incorporates 2 solutions (for example 6 and 18 as shown in set 1) and makes the y position of the vertex always be at y = 10? Again I'm looking for an equation that will do this for any 2 solutions.
If you would like more clarification, ask and I will try to provide some more information. Any help is appreciated!

REPLY [0 votes]: Let's define some terms that will help with the question.
The roots or zeros of a polynomial of degree $n$ are the solutions to the polynomial. On a graph, they are shown as the $x$-intercepts.
The 'vertex' of a quadratic graph is called a turning point, which can be minimum or maximum. It is the point which the gradient is equal to zero.

A useful form of writing a quadratic is called the turning point form, which is what you need at the moment. Turning point form is said to be written in the form:
$$y = a(x-h)^2+k$$
where $a$ measures the width of the parabola, and $(h,k)$ is the turning point of the graph.
If you are looking for a quadratic which has its turning point at $y=10$, then any quadratic will be in the form
$$y = a(x-h)^2 + 10$$
Any real value of $h$ will work, but $a$ must be negative - this reflects the graph along the x-axis. By doing this, the graph is upside-down (we call this concave down) and there will always be two solutions.
Therefore, to complete your problem, a quadratic in the form $y=a(x-h)^2+k$ such that $a<0$, $k=10$ will give a turning point at $y=10$ with two distinct solutions.
You can always expand the brackets to get to the normal quadratic form $y = ax^2 + bx + c$.

Let's do an example: let $a=-2$ and $h=3$ and $k=10$.
then $$y=-2(x-3)^2+10$$
the graph of $-2x^2+12x-8$ looks like this.


TITLE: Zero Sum game how to find NE in pure and mixed strategy
QUESTION [0 upvotes]: The zero sum game matrix as follows
  p   q   r
T 5   3   y
B 9   5  9y

The question is to find all the NE in pure and mixed strategy by using different case distinctions values of y
Can you please explain how to approach this? For example if y=1

REPLY [0 votes]: HINT
Assuming the $p,q.r$ chooser is the minimizer, $q$ always dominates $p$. Then since you cannot find any $y$ such that $y>3$ but $9y < 5$, the two by two sub-game involving strategies $q$ and $r$ will always have a saddle point (pure strategy at equilibrium).
For what value(s) of $y$ does that saddle point change to a different element of the game matrix?


TITLE: Countability of the set of all finite weighted graphs.
QUESTION [0 upvotes]: Let $G_{w}$ be the set of all wighted graphs $(G,f)$ with $G = (V,E)$, $V = \{1,...,n\}$ for an $n \in \mathbb N$ and $f: E \to \mathbb N$ the wight function.
I need to prove or disprove that the set is countable.
This is how I proceeded:
assume that $G_{w}$ is countable, then we can make a list of all the graphs in the set, so an injection $G_{w} \to \mathbb N$. Let now $G_{n}$ be the n-th graph in the list. We construct a new weighted graph
$G'_{n}  = (V',E')$
$V' = V + \{ v_{new}\}$
$E' = E + \{v_{new},u\}$
$f'(\{v_{new},u\}) = m$ for some number $m \in \mathbb N$
this new graph is obvoiusly also in $G_{w}$ but not in our list per construction. So we arrive at a contradiction and therefore the set $G_{w}$ is not countable.
is this proof correct? please help I'm not sure. I also had the idea of trying to construct a similar proof with the set of all possible wight functions f. Since f is injective and the edge set is always finite, I was not sure if the set of all the weight functions is also uncountable.
Thank you for your help
Alternative idea:
We know that the set of all possible edges between finitely many verices is countable. Since for each vertex from the finite set $\{1,...,n\}$ we assign it to a vertex from the finite set $\{1,...,n\}$. So the set of all possible edges is countable since we have a bijection.
Now for each edge, we assign a number to it via a weighting function $f$. There are countable many such possible weightings. A function $f: E \to \mathbb N$ is injective.
so in total we have countable many possibilities, hence the set $G_{w}$ is countable.

REPLY [4 votes]: As far as I understand, you're simply adding a new weighted edge between a new vertex and some other vertex in the $G_n$. There is no reason this graph cannot be in your list.
In any case, the set is countable, assuming your graphs are simple. There are finitely many simple graphs of $n$ vertices for every $n \in \mathbb{N}$, and for each graph countably many weighting functions. So you get a countable union of countable sets, which is countable.


TITLE: Prove that $\lim\limits_{x\to \infty} a\sqrt{x+1}+b\sqrt{x+2}+c\sqrt{x+3}=0$ if and only if $ a+b+c=0$
QUESTION [4 upvotes]: Prove that
$$ \displaystyle \lim_{x\to\infty } \left({a\sqrt{x+1}+b\sqrt{x+2}+c\sqrt{x+3}}\right)=0$$
$$\text{if and only if}$$
$$ a+b+c=0.$$. I tried to prove that if $a+b+c=0$, the limit is $0$ first, but after getting here i got stuck
$$\lim_{x\to\infty } \left({\sqrt{x+1}\left(a+b\sqrt{1+\frac{1}{x+1}}+c\sqrt{1+\frac{2}{x+1}}\right)}\right)$$
Got here by substituting $\sqrt{x+2}$ with $\sqrt{(x+1)(1+\dfrac{1}{x+1})}$
Edit: x tends to infinity, not to 0. I transcribed wrongly.

REPLY [0 votes]: Lessee...
first prove $\lim_{x\rightarrow \infty}\frac{\sqrt {x + j}}{\sqrt{x+k}}= 1$ which should be easy (albeit tedious) enough. [$\frac{\sqrt{x + j}}{\sqrt{x + k}} =\frac{ \sqrt{1 + j/x}}{\sqrt{1 + k/x}}$ so limit is 1].
$\lim_{x\rightarrow \infty}a\sqrt{x + 1} + b \sqrt{x+2} + c\sqrt{x+3} =$
$\lim_{x\rightarrow \infty}(a + b\frac{\sqrt{x+2}}{\sqrt{x+1}} + c\frac{\sqrt{x+3}}{\sqrt{x+1}})\sqrt{x+1}=$
$\lim_{x\rightarrow \infty}(a + \lim_{x\rightarrow \infty}b\frac{\sqrt{x+2}}{\sqrt{x+1}} + \lim_{x\rightarrow \infty}c\frac{\sqrt{x+3}}{\sqrt{x+1}})\sqrt{x+1}=$
$\lim_{x\rightarrow \infty}(a + b + c)\sqrt{x+1}=$
$(a + b + c)\lim_{x\rightarrow \infty}\sqrt{x+1}=$
$\{\sqrt{x+1}\}$ diverges. So If $a + b + c \ne 0$ then $\{(a + b + c)\sqrt{x+1}\}$ diverges.
If $a + b + c = 0$ then $\lim_{x\rightarrow \infty}(a + b + c)\sqrt{x+1}=\lim_{x \rightarrow \infty} 0 = 0.$


TITLE: Find angle in a figure involving a scalene triangle
QUESTION [3 upvotes]: $\triangle ABC$ is a scalene triangle and $\overline {AM}$ is the median relative to the side $\overline {BC}$. A circumference of diameter $\overline {AM}$ intersects by the second time sides $\overline {AB}$ and $\overline {AC}$ at points P and Q, respectively, both different from A. Assuming that $\overline {PQ}$ is parallel to $\overline {BC}$, find the measure of angle $\angle BAC$.

Background: I'm a 9th grader who has some experience in math contests. This is question 5 (level 2), from the 2013 Brazilian Math Olympic (OBM). The answer was not given, and I believe that it's impossible to find a solution, given that $\triangle ABC$ cannot be scalene in the conditions given by the question, but I'm not sure.
My attempt:
(1)Using the information given in the question and considering that the circumference intersects the sides of the triangle is at point A, I came up with
(2)$\overline {CB}$ is tangent to the circle, so:
$$\angle AMB=\angle AMC=90°$$
(3)Point M is the midpoint of $\overline {BC}$, so:
$$\overline {CM}=\overline {BM}$$
Using (1), (2), and (3), I can conclude that $\triangle ABC$ is isosceles, which contradicts the statement in the question, in which it is stated that $\triangle ABC$ is scalene.
Question: Did I interpret something wrong? Is it impossible to find a scalene triangle that complies with the statement? Any help is appreciated.

REPLY [5 votes]: Don't let the diagram fool you. It does not follow from the given information that the circle is tangent to side BC at M.
Here is another way to draw the diagram which should give you a hint about how to find the angle:

I have created a Geogebra web page where you may experiment with the triangle.
Move the vertices of the triangle here.


TITLE: Epimorphism of linear transformation
QUESTION [1 upvotes]: Find values of parameter t for which transformation is epimorphic:
$\psi([x_1,x_2,x_3,x_4])=[x_1+x_2+x_3+2x_4,x_1+tx_2+x_3+3x_4,2x_1+x_2+tx_3+3x_4] $
When this transformation is epimorphic i.e. what should i look for in the reduced form of matrix of this linear transformation?

REPLY [0 votes]: Hint
Epimorphisms must satisfy

$\phi$ is linear (this is the case for all $t$, since $\phi$ can be represented by a matrix-vector multiplication)
$\phi$ is surjective (that means that $\phi(\mathbb R^4) = \mathbb R^3$, i.e. $\mathrm{rank}(\phi) = 3$)

So you must check whether the matrix
$$[\psi] = \pmatrix{1&1&1&2\\1&t&1&3\\2&1&t&3}$$
Has rank $3$ (in general: full row rank). This is the case iff the REF of $[\phi]$ has the form
$$[\psi] \sim \pmatrix{1&0&0&\ast\\0&1&0&\ast\\0&0&1&\ast}$$
(in general: $[\psi]\sim\pmatrix{I_n &\ast}$ where $n$ is the number of rows)


TITLE: Operator Norm Question
QUESTION [2 upvotes]: Suppose I am interested in operators $T:X\to Y$, with $X$ and $Y$ both separable Hilbert spaces.  The operator norm of such $T$ can then be taken as
$$
\|T\| = \sup_{\|x\|_X\leq 1}\|Tx\|_Y.
$$
Since the spaces are separable, there exists a sequence $\{x_n\}$ and $\{y_m\}$ dense in the unit balls of $X$ and $Y$.  It would appear then, that we can write
$$
\|T\|=\sup_{n}\sup_m |(Tx_n,y_m)_Y| = \sup_{m}\sup_n |(Tx_n,y_m)_Y|.
$$
In the above, I am representing the $Y$ norm as
$$
\|y\|_Y = \sup_{\|\tilde y\|\leq 1}|(y,\tilde y)_Y|
$$
Is there anything wrong with this intuition?

REPLY [1 votes]: Your equation
$$
\|T\|=\sup_{n}\sup_m |(Tx_n,y_m)_Y| = \sup_{m}\sup_n |(Tx_n,y_m)_Y|.
$$
is indeed correct.
It works because the relevant norms are continuous and because of the density of the sequences in the unit balls.


TITLE: X,Y random variables joint pdf
QUESTION [0 upvotes]: I have two random variables $X$ and $Y$ that have joint pdf $f_{X,Y}(x,y)$. Why would the pdf of $X+Y$ be $f_{X+Y}(z)=\int_{-\infty}^{\infty}f_{X,Y}(x,z-x)dx$. I dont see why this is true. Would this also be true if $X$ and $Y$ were independent, I think that the pdf of $X+Y$ would also be this but im not sure.

REPLY [1 votes]: The reason this is true:
For any given $z$, the probability that $X+Y=z$ is precisely the probability that $X=x$ for ANY value $x$, and that $Y=z-x$. This is precisely the meaning of the integral given: you "sum up" over all $x$s, the density of the event $\{X=x,Y=z-x\}$.
In the case where $X$ and $Y$ are independent, this statement is still definitely true; however, you can say better!  If $X$ and $Y$ are independent, then you can write
$$
f_{X,Y}(x,y)=f_X(x)\cdot f_Y(y)
$$
where $f_X$ and $f_Y$ are the (separate) densities for $X$ and $Y$, respectively.  As such, you can write
$$
f_{X+Y}(z)=\int_{-\infty}^{\infty}f_{X,Y}(x,z-x)\,dx=\int_{-\infty}^{\infty}f_X(x)f_Y(z-x)\,dx.
$$
This is called the convolution of $X$ and $Y$.