User daizhuo - MathOverflow

How to characterize real square matrices A, such that v'Av >= 0, for all real vectors v with 1'v=0 (1 is the vector of all ones)?

2010-11-04T03:21:47Z

I derive this question while trying to prove the monotonicity of a differentiable vector function $f(x)$ that maps from $X\subset R^n$ to $R^n$ (Here function $f(x)$ is called monotone if $(x-y)'(f(x)-f(y))\geq 0$, $\forall x,y\in X$). The domain $X$ only consists of vectors $x$ such that $1'x=0$, here $1$ is the vector of all ones.

Using the mean-value theorem, we have that $f(x)$ is locally monotone at $x$ (namely $(y-x)'(f(y)-f(x))\geq 0$, $\forall y\in X$) if its Jacobian matrix evaluated at $x$, which we label as $A$, satisfies the following condition:

$$v'Av\geq 0,\quad \forall v \text{ such that } 1'v=0.$$

This is a weaker condition than positive semidefiniteness. However, while there are a number of ways to characterize positive semidefinite matrices, for example, see this Wikipedia page, how can I characterize the above defined matrices?

How to write Matlab's dot operators in mathematical expressions?

2010-07-19T17:20:11Z

Matlab has a set of dot operators, such as .*, ./, .^. Each of these operators consists of a dot and a normal algebraic operator. They perform element-wise algebraic operations on a matrix. For example, consider the following codes

A = [1 2 3; 3 2 1];
x = [1 2 4];

B = A.^2
y = 1./x

The result is

B =

     1     4     9
     9     4     1

y =

     1.0000    0.5000    0.2500

I find these dot operators very convenient. My question is, how to write these dot operators in mathematical expressions? (By mathematical expressions, I mean the expressions used in proofs.)

EDIT - One obvious way is to define the result matrix element-wise. But is there a way to write this result in a more compact manner?

Expectation, multinomial distribution, and monotonicity (A conjecture)

2010-12-01T10:40:22Z

Let $n$ and $k$ be two positive integers. Let $S = \{ \mathbf{p} \in \mathbb{R}^k : \mathbf{p} \geq 0, \sum_{i=1}^k p_i = 1 \}$ (i.e., a simplex). Consider a function $\mathbf{f}:\mathbb{Z}^k \rightarrow \mathbb{R}^k$. And from $\mathbf{f}$ we may define function $\mathbf{g}: S\subset \mathbb{R}^k \rightarrow \mathbb{R}^k$ as follows $$\mathbf{g}(\mathbf{p}) = \mathbb{E}[\mathbf{f}(\mathbf{X})], \quad \mathbf{X}\sim \text{Multinomial}(n,\mathbf{p}).$$ Here $\mathbf{X}$ is a random vector that follows the multinomial distribution determined by the number of trials $n$ and probabilities $p_1,p_2,\dots,p_k$.

Conjecture: If $\mathbf{f}$ is monotone, that is, $$ (\mathbf{x}-\tilde{\mathbf{x}})^T (\mathbf{f}(\mathbf{x})-\mathbf{f}(\tilde{\mathbf{x}})) \geq 0\quad \forall \mathbf{x}, \tilde{\mathbf{x}} \in \mathbb{Z}^k,$$ then $\mathbf{g}$ is also monotone, i.e., $$ (\mathbf{p}-\tilde{\mathbf{p}})^T (\mathbf{g}(\mathbf{p})-\mathbf{g}(\tilde{\mathbf{p}})) \geq 0\quad \forall \mathbf{p}, \tilde{\mathbf{p}} \in S.$$

Remark: The above result should hold in the following two special cases (I omit the proofs) -

The function $\mathbf{f}$ is affine, namely, $\mathbf{f}(\mathbf{x})=G\mathbf{x}+\mathbf{b}$ for some matrix $G$ and vector $\mathbf{b}$.
The function $\mathbf{f}$ is "separable", meaning that $$\mathbf{f}(\mathbf{x}) = (f_1(x_1), \dots, f_k(x_k))^T$$ for some non-decreasing scalar functions $f_1(\cdot), \dots, f_k(\cdot)$.

But does it hold in the general case?

For what k, matrix (k A - B) is positive semidefinite?

2010-11-29T02:39:35Z

Suppose $A$ and $B$ are two $n\times n$ real symmetric matrices. $A$ is positive semidefinite. Then for what values of real number $k$, matrix $(kA-B)$ is positive semidefinite (we write as $kA-B\succeq0$)?

If $A$ is positive definite, we may find an $n\times n$ nonsingular matrix $D$ such that $A=D^T D$. As a result, $kA-B\succeq0$ is equivalent to $$kI\succeq (D^{-1})^TBD^{-1},$$ or $k\geq \lambda_{\max}((D^{-1})^TBD^{-1}))$.

But how to deal with the situation when $A$ is singular (but still positive semidefinite)? I know for certain that in this case we must impose additional constraint on matrix $B$. In particular, let the columns of matrix $N$ consist of a basis of the null space of $A$, then we must have that $N^T B N \preceq 0$ (i.e., $N^T B N$ is negative semidefinite). But what is the lower bound on $k$?

Thanks.

Comment by daizhuo

2010-11-30T17:35:26Z

Thanks. In fact, $B_{13}$ must be 0. Let $P_1$ be a matrix consisting of columns that form a basis of the range of $A$. Let $P_2$ be a matrix consisting of columns that form a basis of the intersection of the kernel of $A$ and the range of $B$. Let $P_3$ be a matrix consisting of columns that form a basis of the intersection of the kernel of $A$ and the kernel of $B$. Then columns of $P=(P_1, P_2, P_3)$ form a basis of $\mathbb{R}^n$ in which $A$ and $B$ took the form you showed above. In particular, $B_{13} = P_1^T B P_3 = 0$ because $B P_3 = 0$.

Comment by daizhuo

2010-11-29T09:56:51Z

Actually $kA - B \succeq 0$ for $k \geq -1$.

Comment by daizhuo

2010-11-29T09:52:11Z

Can you be more specific on your last sentence? In particular, why do I need $\text{ker}A\subseteq\text{ker}B$? A counter example would be the following. $A = \left(\begin{array}{cc}1 & 0\\0 & 0\end{array}\right)$ and $B = -I$. In this case $k A - B\succeq 0$ for $k\geq 0$, but $\text{ker}A$ is larger than $\text{ker} B$.

Comment by daizhuo

2010-11-05T03:34:00Z

Thanks for your comment. I added to my question the definition of vector function monotonicity.

Comment by daizhuo

2010-07-20T02:06:01Z

Thanks for the comment. I followed the link to APL; it is interesting!

Comment by daizhuo

2010-07-19T17:57:25Z

Oh thanks for your response! But are there more compact ways to write these facts?