User jeremy west - MathOverflow

Is there a name for this type of matrix? (Reference Request)

2011-07-22T22:02:28Z

I am working on a problem were I encounter matrices of the form

$X = \begin{bmatrix}\frac{1}{1 - a_ib_j}\end{bmatrix}_{ij}$

I am aware of Cauchy matrices, which have the form

$X = \begin{bmatrix}\frac{1}{a_i - b_j}\end{bmatrix}_{ij}$

(sometimes written with a plus rather than a minus). Many of the results I need I can actually obtain by factoring the above matrix as a product of a diagonal matrix with a Cauchy matrix (assuming the $a_i \neq 0$), as in:

$X = \mathbb{diag}(a_i^{-1})\begin{bmatrix}\frac{1}{a_i^{-1} - b_j}\end{bmatrix}.$

These matrices arise when computing solutions to matrix equations of the form

$X - AXB^T = C$

which are discrete-time analogs of Sylvester equations:

$AX + XB = C.$

(Also, related are Lyapunov equations and algebraic Riccati equations). It seems that these must appear in the literature somewhere, but I haven't been able to find them. My question is:

Do matrices of the form $X = \begin{bmatrix}\frac{1}{1 - a_ib_j}\end{bmatrix}_{ij}$ have a name in the literature?

Is anyone aware of good references for general results on these matrices? For example, there are general results on the determinant and inverses of Cauchy matrices.

As I mentioned, I have already found a determinant formula and a formula for the inverse of the matrix using the factorization I mentioned above. But it would be helpful to know of further results if they exist and I would like to properly cite the literature as well.

Answer by Jeremy West for Is it true that a set is countable if and only if there exists a Turing machine to enumerate all the elements in the set?

2011-03-09T05:14:05Z

I would say no. If there is such a machine then the set is obviously countable. But for the other direction, there are many countable subsets of non computable real numbers. Unless you relax sufficiently your definition of enumeration (What finite string would the Turing machine output to represent a non computable number, or any irrational number for that matter?) then I don't see how such a Turing machine could enumerate any of these sets.

Answer by Jeremy West for Why do we teach calculus students the derivative as a limit?

2010-11-07T06:31:10Z

A problem I like to give students to solve shortly after introducing the derivative is to evaluate $f'(2)$ for $f(x) = x^x$. Of course, this function can be rewritten as $f(x) = e^{x\ln x}$ but in my experience students don't think of this. In fact, students who have seen Calculus before almost universally reach the solution $f'(2) = 4$ which they get from the mistaken idea that $f'(x) = x\cdot x^{x-1} = x^x$. The only students that usually get this problem correct are those that haven't yet learned any of the computational methods and only know the definition.

I teach the limit definition and emphasize the physical and geometric interpretations, and then move from that to the concept of the tangent line and linear approximation. I think these concepts encapsulate most of what is significant (intuitively) about the definition. I dislike exam questions that require students to compute derivatives using the limit definition when they know a "better" way to do it. It isn't too hard to write a problem where no formula for the function is given and ask students questions about the sign or approximate magnitude of the derivative or whether or not the function should even have a derivative. For students who to do not intend to pursue mathematics, this seems appropriate to me. Even those who become mathematicians will almost surely see these ideas again in complete detail in an elementary analysis course.

What is the order of a in (Z/nZ)*?

2010-10-28T23:13:45Z

I was recently thinking about efficient algorithms for modular exponentiation. This led me to the (more interesting, in my opinion) question:

Let $1 < a < n$ be an integer relatively prime to $n$. What is the order of ${\overline{a}}$ in $\mathbb{Z}/n\mathbb{Z}^*$ (the multiplicative group of $\mathbb{Z}/n\mathbb{Z}$)?

I did some Google searching, but all I could find were the obvious facts that the order should divide the order of the group $\phi(n)$ and the exponent of the group $\lambda(n)$ (see Carmichael function). I asked several people if anything more could be said, but the answers were generally: "Some people study this. It is really hard." However, I couldn't find any other references.

Is this a question that has been seriously considered? If so, what is known and does anyone have any good references?

I am happy to suppose that we know a priori the prime factorization of both $a$ and $n$. Even given this information, is there something precise that can be said?

Because this is a (potentially) open problem, it is possible that it should be a community wiki page, I am not entirely certain what the policy is there. If so, someone please wiki-hammer this, as I have not the power! It might also be deserving of the open-problem tag?

Edit: I do in fact have the power to make community wiki posts (which I discovered by checking the faq) just not to edit someone else's. Still, I would prefer that this be a "real" question unless that is inappropriate.

Answer by Jeremy West for Extremely messy proofs

2010-10-27T16:20:30Z

This is not about measure theory or Dynkin's lemma or Caratheodory's extension theorem, but it is hard for me to resist sharing one of my favorite examples of improving proofs with modern machinery: the Intermediate Value Theorem. This theorem is so intuitively obvious, but the proof using classical analysis involves taking a supremum of the set of $a \leq x \leq b$ such that $f(x) \leq y$ (where $y$ is the desired output) and then showing using continuity that this supremum $c$ satisfies $f(c) = y$. There are lots of $\delta$'s and $\epsilon$'s and the proof feels uninspiring and technical at best.

Enter topology. The proof that the image of a connected set is connected for a continuous function is simple and intuitive, as is the notion of a connected set. Once this is established, the Intermediate Value Theorem is essentially just the statement that an interval is a connected set, so the image must be connected. This proof captures, in my opinion, the intuition of the Intermediate Value Theorem in a precise way.

Answer by Jeremy West for Decomposing the plane into intervals

2010-10-26T01:53:57Z

Start with the collection of half-open intervals of the form $[a,a+1) \times 0$ where $a \geq 0$ is an integer. This decomposes the positive $x$-axis into half-open intervals. Now, for every value of $0 < \theta < 2\pi$, decompose the ray whose angle with the positive $x$-axis is $\theta$ into half-open intervals with the open end of the interval placed at the endpoint nearest the origin.

Examples of DVRs of residue char p and ramification e

2010-10-24T23:47:56Z

I am looking for concrete examples of a complete discrete valuation ring $R$ of characteristic 0, residue characteristic $p$ and ramification index $e$. By residue characteristic, I mean the characteristic of the field obtained by the quotient of $R$ with its unique maximal ideal $M$ and by ramification index I mean the largest positive integer $e$ such that $M^e \supseteq pR$.

Without the restriction on the ramification, a simple example is the $p$-adic integers $\mathbb{Z}_p$. However, when we try to fix the ramification index, this becomes more challenging. For example, with $e = 2$ we can take $R = \mathbb{Z}_p[\sqrt{p}]$. The maximal ideal of this ring is $M = \sqrt{p}R$ which has ramification index 2.

My question: is there a simple construction for such a ring with arbitrary $p$ and $e$? If not, can an infinite family of such rings be constructed that have a known ramification index $e > 2$?

Comment by Jeremy West

2012-06-20T20:58:25Z

I've seen it used (and used it myself) with the Kalman filter. Matrices of that form come up when dealing with covariance matrices, particularly for normal distributions. See, for example, math.byu.edu/~jeffh/publications/papers/HW1.pdf

Comment by Jeremy West

2011-07-26T19:07:39Z

Thank you Federico. I apologize for the mistake.

Comment by Jeremy West

2011-07-22T22:07:53Z

Should the random walk be $S_k = sum_{i=1}^k D_i$?

Comment by Jeremy West

2011-03-09T04:36:26Z

It might also be worth mentioning that if P = NP and a sufficient length $n$ for a proof is known, then (you can show that) a proof of that length can be constructed in polynomial time. This would give us some proof of the theorem besides the correctness of the machine that Daniel mentions. Whether that proof is "understandable" is subjective.

Comment by Jeremy West

2011-03-09T04:32:31Z

@Daniel Litt, @Thierry Zell I am pretty sure that the parameter $1^n$ that Daniel mentions is essential for this language to be (obviously) in NP. Perhaps I am being dense, but even supposing P = NP I don't see a practical way to determine whether a given theorem is true; you still have to choose the correct (large enough) value of $n$. Maybe there is a nice way to bound it? I don't doubt Cook's claim per se, I just don't see yet how it would work.

Comment by Jeremy West

2011-03-09T00:33:02Z

I'm still very confused as to precisely what the language is that such a Turing machine is deciding that we are claiming is in NP. What is the input exactly?

Comment by Jeremy West

2011-02-23T03:55:50Z

Although W3C has some great standards documents that should enhance the reliability and universality of the internet, the web is still full of noncompliant pages and proprietary technology. I have to assume the same would happen in the mathematics community, even if precise standards were adopted.

Comment by Jeremy West

2011-02-01T05:18:08Z

What an excellent observation (lossy translation notwithstanding)!

Comment by Jeremy West

2011-02-01T05:06:41Z

@Michael Also, lest I seem antagonistic, I thought the original question was excellent, which is why I remembered when I read this one.

Comment by Jeremy West

2011-02-01T05:01:45Z

@Michael "Serious" = "Worth learning" is vague and subjective. I disagree that your examples would convince students that there are interesting and important open problems in math: none of them are open! I commented about your previous question because I intended to link to it and was surprised to see that you asked it. From the length of the question it seemed you saw it as something different, which made me wonder if I had misunderstood it. For the record, I did read the entire question.

Comment by Jeremy West

2011-02-01T02:47:40Z

I wish I could up-vote this a few more times (I know, I'm really slow reading this one)!

Comment by Jeremy West

2011-02-01T01:51:32Z

What do you mean exactly by a "serious problem"? Also, is this question significantly different than your previous question? mathoverflow.net/questions/28695/…

Comment by Jeremy West

2010-12-16T21:11:25Z

This wasn't my question, but this answer was uncommonly informative. Thanks!

Comment by Jeremy West

2010-12-06T18:21:56Z

I realize I am very late to the party here, but I couldn't resist commenting that the high school student I am currently tutoring is required to do these types of proofs. In fact, when I explain to people that research mathematicians prove theorems, the most common response I get is "I hated doing proofs in geometry!" Upon examination, I always find that they did two-column proofs, and this is their only association with the term.

Comment by Jeremy West

2010-11-11T18:13:53Z

I only meant that they would numerically estimate it at x = 2 using the limit definition. It is easy to estimate using the definition, but if they try to differentiate and plug in 2 they will probably get the wrong answer.