博客

证明V的两个子空间的并是V的子空间当且仅当其中一个子空间包含另一个子空间

Question:

Prove that the union of two subspaces of \(V\) is a subspace of \(V\) if and only if one of the subspaces of \(V\) is contained in the other.

证明V的两个子空间的并是B的子空间当且仅当其中一个子空间包含领一个子空间。

Solution:

Assume two set A, B are subspaces of \(V\).

Part 1:

Assume \(A \cup B = A\) or \(B\).

Clearly \(A \cup B = A\) or \(B \in V\).

Therefor if one subspace of \(V\) is contained in the other, the union of two subspaces is a subspace of \(V\).

Part 2:

Assume \(A \cup B \neq A\) or \(B\).

Now we take \(a \in A\) but not in \(B\), and \(b \in B\) but not in \(A\).

Since \(a \in A\), we know \(-a \in A\).

Assume \(a + b \in A\).

As we know, \(A\) is a subspace of \(V\). So \(A\) is closed under addition.

Therefor, \((a + b) + (-a)\) should be in A.

But in fact, \((a + b) + (-a) = b\). We have assumed that \(b \notin A\). We have reached a contradiction on the assumption that \(a + b \in A\). Thus \(a + b \notin A\).

If we assume \(a + b \in B\), we will also reach a contradiction like this.

Therefor, \(a + b\) is not in A and B.

i.e. \(a + b \notin A \cup B\).

Then the set \(A \cup B\) isn’t closed under addition.

Therefor if \(A \cup B \neq A\) or \(B\), \(A \cup B\) is not a subspace of V.

Now we have proved that the union of two subspaces of \(V\) is a subspace of \(V\) if and only if one of the subspaces of \(V\) is contained in the other.

R到R的周期函数构成的集合是R^R的子空间吗?

Question:

A function \(f : \mathbb{R} \rightarrow \mathbb{R}\) is called periodic if there exists a positive number \(p\) such that \(f(x) = f(x + p)\) for all \(x \in \mathbb{R}\). Is the set of periodic functions from \(\mathbb{R} \rightarrow \mathbb{R}\) a subspace of \(\mathbb{R}^{\mathbb{R}}\)? Explain.

Solution:

The answer to this question is YES. Now we will prove it.

Let \(V\) be the set of all periodic functions from \(\mathbb{R} \rightarrow \mathbb{R}\).

Part 1:

Let \(f_0(x) = 0\). Clearly \(f_0 \in V\).

Part 2:

Take \(f, g \in V\), \(f(x + m) = f(x)\), \(g(x + n) = g(x)\).

Clearly, \(\begin{aligned}(f + g)(x + lcm(m, n)) = & f(x + lcm(m, n)) + g(x + lcm(m, n)) \\ = & f(x) + g(x) \\ = & (f + g)(x)\end{aligned}\).

Thus \(f + g \in V\).

Part 3:

Take \( f \in V\), and \(a \in R\).

We have \((af)(x + p) = a \cdot f(x + p) = a \cdot f(x) = (af)(x)\).

Thus \(af \in V\).

Therefor the set of all periodic functions from \(\mathbb{R} \rightarrow \mathbb{R}\) is a subspace of \(\mathbb{R}^{\mathbb{R}}\).

给出R^2的一个非空子集U的例子,使得U对于加法是封闭并且具有加法逆元的,但U不是R^2的子空间

Question:

Give a example of a nonempty subset \(U\) of \(\mathbb{R}^2\) such that \(U\) is closed under addition and under taking additive inverses but U is not a subspace of \(\mathbb{R}^2\).

Solution:

Consider the subset \(\mathbb{Z}^2\). This set is closed under addition, as we will get an integer if we add one integer to another integer. But if we assume \(a = \sqrt{2}\) and \(u = (1, 1) \in \mathbb{Z}^2\), we have

\(a \cdot u = \sqrt{2} \cdot (1, 1) = (\sqrt{2}, \sqrt{2}) \notin \mathbb{Z}^2\).

 

 

类似问题:

给出R^2的一个非空子集U的例子,使得U在标量乘法下是封闭的,但U不是R^2的子空间。

给出R^2的一个非空子集U的例子,使得U在标量乘法下是封闭的,但U不是R^2的子空间。

Question:

Give an example of a non-empty subset \(U\) in \(R^2\) such that \(U\) is closed under scalar multiplication, but \(U\) is not a linear subspace of \(R^2\).

 

Solution:

Let \(U\) = {\((x, y) | x = 0 or y = 0\)}.

Now we take \(u \in U, a \in \mathbb{R}\).

If \(u = (x, 0)\), then \(a \cdot u = (ax, 0) \in U\).

If \(u = (0, y)\), then \(a \cdot u = (0, ay) \in U\).

Therefor, U is closed under scalar multiplication.

 

If a subset U is a subspace, it need to satisfy:

  1. \(0 \in U\).        (This is what we called additive identity)
  2. If \(u, v \in U\), \(u + v \in U\).        (i.e. \(U\) is closed under addition)
  3. U is closed under scalar multiplication.

Now we have proved that \(U\) is satisfied the 3. To prove \(U\) isn’t a subspace of \(R^2\), we need to prove that U is failed to satisfy 1 or 2.

Note that if we take \(u \in U\) and \(a = 0\), we have \(a \cdot u = 0\). Since we have proved that U is closed under scalar multiplication, now we prove \(0 \in U\).

Because 2 implies 1 if U is a non-empty space, we have to find a U which isn’t closed under addition.

For \(U\) = {\((x, y)\) | \(x = 0\) or \(y = 0\)}, we find that if \(u = (x, 0)\), \(v = (0, y)\), \(u + v = (x, y) \notin U\).

Now we find a example {\((x, y)\) | \(x = 0\) or \(y = 0\)} that isn’t a vector space of \(R^2\).

 

 

类似问题:

给出R^2的一个非空子集U的例子,使得U对于加法是封闭并且具有加法逆元的,但U不是R^2的子空间

Is {(a, b, c) in F^3 : a^3 = b^3} a subspace of F^3? (the F is R and C)

There are two question to be solved:

1. Is {\((a, b, c) \in \mathbb{R}^3 : a^3 = b^3\)} a subspace of \(\mathbb{R}^3\)?

2. Is {\((a, b, c) \in \mathbb{C}^3 : a^3 = b^3\)} a subspace of \(\mathbb{C}^3\)?

Solution to question 1:

Let \(V\) = {\((a, b, c) \in \mathbb{R}^3 : a^3 = b^3\)}.

Part 1, additive identity:

Obviously \(0 = (0, 0, 0) \in V\).

Part 2, closed under addition:

Take \(u, w \in V, u = (u_1, u_2, u_3)\) and \(w = (w_1, w_2, w_3)\).

We have \(u_1^3 = u_2^3, w_1^3 = w_2^3\).

Thus \(u_1 = u_2, w_1 = w_2\)        (1-2-1).

Now we have \(u + w = (u_1 + w_1, u_2 + w_2, u_3 + w_3)\).

According to formulas (1-2-1), we get \(u_1 + w_1 = u_2 + w_2\)

(i.e. \((u_1 + w_1)^3 = (u_2 + w_2)^3\)).

Therefor \(u + w \in V\).

Part 3, closed under scalar multiplication:

Take \(u \in V, u = (u_1, u_2, u_3),\) and \(a \in \mathbb{R}\).

We have \(au = a(u_1, u_2, u_3) = (au_1, au_2, au_3)\).

Clearly, \((au_1)^3 = (au_2)^3 \leftrightarrow u_1^3 = u_2^3\).

Therefor \(au \in V\).

Therefor {\((a, b, c) \in \mathbb{R}^3 : a^3 = b^3\)} is a subspace of \(\mathbb{R}^3\).

Solution to question 2:

The key to the answer of this question is that for \(a, b \in \mathbb{C}\), we can’t deduce \(a = b\) from \(a^3 = b^3\). Therefor, if we take

\(u, w \in\) {\((a, b, c) \in \mathbb{C}^3 : a^3 = b^3\)},

and assume \(u = (u_1, u_2, u_3), v = (v_1, v_2, v_3)\), we can’t deduce \((u_1 + v_1)^3 = (u_2 + v_2)^3\) from \(u_1^3 = u_2^3 and v_1^3 = v_2^3\).

Thus {\((a, b, c) \in \mathbb{C}^3 : a^3 = b^3\)} isn’t closed under addition.

i.e. {\((a, b, c) \in \mathbb{C}^3 : a^3 = b^3\)} is a subspace of \(\mathbb{C}^3\).

ZWK线段树

前言一:

建议在阅读这篇博客前,首先会实现普通的递归线段树。

前言二:

此方法非本人所创,为从其他人博客学习而来。普通用途下(如求和、RMQ等),这个方案能够获得比普通线段树更少的时间消耗,但是使用时也有一些细节值得注意(详见正文),经过几次掉入这些细节的坑中后,我决定将它记录下来。

正文:

首先,我们需要回忆一下一般线段树的点更新操作过程:

假设要构建对一个包含8个元素的数组进行更新与求和的线段树,

假设数组元素序号区间范围是[0, 7],并且现在需要更新2号元素,于是,我们按着:

\([0, 7] \rightarrow [0, 3] \rightarrow [1, 3] \rightarrow [1, 2] \rightarrow [2, 2]\)

这样的深入顺序寻找到了目标位置。

类似的,求任意区间的和,比如[2, 5]便是将表示区间为[2, 2], [3, 3], [4, 5]的三个结点存储的值求和,便得到了数组元素[2, 5]的和。

接下来讨论一下如何不使用递归来构建这棵线段树。首先我们需要将区间转化一下,以方便接下来的操作,按照上边的例子,元素序号的区间范围是[0, 7],在序号都是整数的情况下,它等价于[0, 8),如果以[0, 8)作为根节点区间,构建出来的线段树将会如下图,是一棵满二叉树:

这里稍稍做一下说明:在上面这张图中,颜色较深的方格表示的是对应结点在线段树数组中的索引,而颜色较浅的方格则表示的是对应结点代表的区间。

我们可以看到,最后一行的八个结点,就是原始数组中的八个数,他们在线段树中的位置是从8开始到15结束的,这是必然的,对于一棵有n片叶子的满二叉树(备注:这便要求n是2的幂),非叶子结点的个数为\(n – 1\),如果根节点索引是1,则从做到右的第一片叶子的索引一定是n。

由于能够直接找到每个数组元素在线段树中的确切位置,对线段树进行初始化、更新、询问的操作就可以从底部向上进行。

现在总结一下这个算法的核心:如果有n个元素,则i号元素在线段树数组中的索引为\(i + n\)。

下面是三个核心函数的C++代码实现:

// 变量n是data数组中元素的个数
// 数组STree就是线段树数组
void build() {
    // 这第一个循环是将存放在data数组中的原始数据存放到每个对应的叶子上
    for (int i = 0; i < n; i++) {
        STree[n + i] = data[i];
    }
    // 接下来开始从底向上遍历一下所有的结点,进行一次初始化
    for (int i = n - 1; i > 0; i--) {
        STree[i] = STree[i << 1] + STree[i << 1 | 1];
    }
}

void update(int idx, int diff) {
    //idx表示第idx号元素,idx + n就是它在线段树数组中对应叶子的索引值
    STree[idx + n] += diff;
    for (idx += n; idx &gt; 1; idx >>= 1) {
        STree[idx >> 1] = STree[idx] + STree[idx ^ 1];
    // 这里进行与1异或的作用是:在这棵满二叉树中,如果一个结点
    // 是左结点,则它的索引值是一个偶数,则右结点的索引就是将其
    // 索引值二进制表示下最低位换成1;反过来,对于一个右结点,它
    // 需要将二进制表示下的最低位换成0.
    }
}
    // 由于为了构建满二叉树时,我们将这棵线段树的区间修改成了左闭右开区间,所以这里getSum函数获得的是区间[from, to)的和
int getSum(int from, int to) {
    int res = 0;
    for (from += n, to += n; from < to; from >>= 1, to >>= 1) {
    // 对于左边界,如果它是一个右结点,由于其父结点包含了不属于求和
    // 区间的左结点,所以应当抛弃,而直接将当前节点的值加入到函数返回值中
        if (from&1)
            res += STree[from++];
    // 对于右边界,考虑到右边界上的值是不计入求和的,如果它是一个右结点,我们就先将索引值减一,得到左结点,接着将左结点的值加入到返回值中。
        if (to&1)
            res += STree[--to];
    }
    return res;
}

 

最后,来讨论一下最开始提到的细节。如果想要正确使用这棵树,就必须保证构造一棵满二叉树,这样才能够保证数组元素序号与线段树叶子的序号的对应关系成立,这个算法才是正确的。

对于任意个数的数据,假设为size,则应有:

\(n = 2^{log_{2}size}\),

将根节点的区间设置为[0, n),第一片叶子的序号是n,树的大小为2 * n – 1.

Prove that the set of continuous real-valued functions on the interval [0, 1] is a subspace of R^[0, 1]

Note Before Proof: 证明一个集合是另外一个集合的子空间,只要证明这个集合具有加法单位元0、加法封闭性、标量乘法封闭性即可。

Prove:

Let V = {\(f | f: [0, 1] \rightarrow R\) such that f is continuous}.

Part 1, additive identity(加法单位元):

Take \(f_{0} = 0 (\forall x \in [0, 1])\). Clearly \(f_{0}\) is continuous and \(f_{0} \in V\).

Part 2, closed under addition(加法封闭性):

Take \(f, g \in V\).

For each \(\epsilon > 0\) and for each \(x \in [0, 1]\) there exists a \(\delta > 0\). Such that if \(|x_{1} – x_{2}| < \delta\), then \(|f(x_{1}) – f(x_{2})| < \frac{\epsilon}{2}\), and \(|g(x_{1}) – g(x_{2})| < \frac{\epsilon}{2}\).

Since \(f + g = (f + g)(x) = f(x) + g(x)\), we have

\(  \begin{aligned} & |(f + g)(x_{1}) – (f + g)(x_{2})|\\= & |[f(x_{1}) – f(x_{2})] + [g(x_{1}) – g(x_{2})]|\\ \le & |[f(x_{1}) – f(x_{2})]| + |[g(x_{1}) – g(x_{2})]|\\< & \epsilon.\end{aligned}\)

i.e. \(f + g\) is continuous at all \(x \in [0, 1]\).

Therefor, \(f + g \in V\).

Part 3, closed under scalar multiplication(标量乘法封闭性):

Take \(f \in V\), and \(a \in R\).

Assume a= 0, then

\((af)(x) = a \cdot f(x) = 0,        x \in [0, 1]\).

Clearly, \(af\) is a continuous real-valued function on the interval [0, 1].

Assume \(a \neq 0\), for each \(\epsilon > 0\) and for each \(x \in [0, 1]\), there exists a \(\delta > 0\) such that if

\(|x_{1} – x_{2}| < \delta\),

then

\(|f(x_{1}) – f(x_{2})| < \frac{\epsilon}{a}\).

Now we have

\(|(af)(x_{1}) – (af)(x_{2})| = |a[f(x_{1}) – f(x_{2})]| = |a|\cdot|f(x_{1}) – f(x_{2})| < \epsilon\).

Therefor, \(af \in V\).

Thus V is a subspace of \(R^{[0, 1]}\).

What is the square root of i?

Solution:

Let \(z = a + bi\) be the complex number which is a square root of i, that is

\(z^{2} = (a + bi)^{2} = a^{2} – b^{2} + 2abi = i\)

Equating real and imaginary parts, we have

\(\begin{cases} a^{2} – b^{2} & = 0,\\ 2ab & = 1.\end{cases}\)

The two real solution to this pair of equations are

\(\begin{cases} a = \frac{1}{\sqrt{2}},\\ b = \frac{1}{\sqrt{2}},\end{cases}\)

and

\(\begin{cases} a = -\frac{1}{\sqrt{2}},\\ b = -\frac{1}{\sqrt{2}}.\end{cases}\)

The two square root of i therefor are \(\pm\frac{1}{\sqrt{2}}(i + 1)\).