Questions on the various algorithms used in linear algebra computations (matrix computations).

learn more… | top users | synonyms

0
votes
1answer
18 views

Is the condition number of unitary matrix always equal to 1?

I know that the 2-norm condition number $\kappa (\textbf U)={||\textbf U||_2}{||\textbf U^{-1}||_2}$ of a unitary matrix $\textbf U$ is always equal to 1. Is this true for all induced matrix norms, i....
0
votes
0answers
28 views

why computing x+1 is stable? [on hold]

I understand it is not backward stable. If we go by definition of stability we get in the numerator Order(machine epsilon) but we have the denominator containing |x(1+delta)+1| where delta is Order(...
1
vote
2answers
32 views

Finding a linear combination with constraints on coefficients

Let there be $n$ unit vectors $\{\boldsymbol{u}_i\}_{1\leq i\leq n }$ in an $m$ dimensional space. The vectors are not necessarily a basis of the space. Let $\boldsymbol{v}$ be a unit vector in the $m$...
0
votes
0answers
22 views

Proving that Newtons Divided difference satisfies a particular formula

Assume $x\neq x_i$ for $0\leq i \leq n$ and show that the divided difference $f[x_0,\ldots,x_n,x]$ satisfies $$f[x_0,\ldots,x_n,x] = \sum_{i=0}^{n}\frac{f[x,x_i]}{\prod_{j=0,j\neq i}(x_i - x_j)}$$ ...
0
votes
0answers
24 views

Linear regression of matrix elements to get the minimal polynomial to perform a matrix inversion?

So each matrix $\bf A$ fulfils an equation for it's minimal polynomial $P_m({\bf A})$: $$P_m({\bf A}) = 0 \Leftrightarrow \sum_{k=0}^{k_n}c_k{\bf A}^k = 0$$ We can by multiplying with $A^{-1}$ and ...
1
vote
0answers
21 views

Stability theorem in numerical eigenvalue problem

This paper mentions the stability theorem in $ 6.1 $ as following: If $ A_{n \times n} $ and $ E_{n \times n} $ are real and symmetric matrix and $ \hat{A} = A + E. $ Let $ \lambda_{1}, \lambda_{2}, \...
2
votes
0answers
23 views

Round-off: cross- vs. dot-products

I have three vectors e0 = numpy.array([1.0, 0.0, 0.0]) e1 = numpy.array([-0.5, 1.0e-4, 0.0]) e2 = numpy.array([0.5, 1.0e-4, 0.0]) (Edges that form a very flat ...
5
votes
2answers
110 views

Compute the main diagonal of $(K + D)^{-1}$ in less than $O(n^3)$ operations

Compute the main diagonal of $(K + D)^{-1}$ in less than $O(n^3)$ operations given full-rank, dense and symmetric matrices $K$ and $K^{-1}$, and a diagonal matrix $D$ with positive elements on its ...
3
votes
0answers
62 views

Upperbound of the ratio of column sums of an integer matrix

Suppose $X_{n \times n}$ is a positive integer matrix where $n\geq 2$. The element in the $i_{th}$ row and $j_{th}$ column of the matrix $X$ is defined as $x_{i,j}$. Now, consider $S_{j,j+1}=argmax_{...
6
votes
1answer
86 views

Compute a diagonalizable matrix close in matrix exponential

It is known that for any matrix $A$, one can perturb $A$ slightly so that the resulting $A(\epsilon)$ is diagonalizable. I am wondering whether for any matrix $A$, $\epsilon>0$, there is an ...
0
votes
1answer
34 views

Derivatives of Matrices and Vectors

I am currently studying deep learning and a lot of the calculus involving differentiating products or sums of ill defined operations on matrices and vectors is very confusing. For instance, take ...
0
votes
0answers
19 views

Singular value decomposition: does the choice of eigenvectors matter?

I'm trying to calculate the SVD-decomposition of a certain matrix, i.e. $ A = U \Sigma V^T$. My solution doesn't yield $A$ again; I just can't get the signs correct. I'm wondering if this is just a ...
0
votes
0answers
14 views

Machine Learning : Proof of equality

currently, I am writing on a paper that also makes use of machine learning techniques. My problem is as follows: I have binary classificator $h_w(\vec{x}^{(i)})$ that simply uses the sigmoid function, ...
1
vote
1answer
36 views

Does Gauss Seidel converge in a finite number of steps

Consider the matrix $$A = \begin{pmatrix} 5 & 0 & 0 & 0 & 0 & 0\\ 1 & 5 & 0 & 0 & 0 & 1\\ 0 & 0 & 5 & 1 & 0 & 1\\ 1 & 0 & 0 & 5 &...
1
vote
0answers
44 views

Divergence when spectral radius is greater than one in an iterative map.

Let $(M_n)$ be a convergent sequence of matrices from $\mathbb{R}^p$ to $\mathbb{R}^p$. Each element of the sequence has the same spectral radius $\sigma$, and $\sigma\ge1$. Show that there exist an $...
0
votes
1answer
27 views

Divergence of an iterative map variant.

The problem at hand. Let $M$ be a matrix from $R^p$ to $R^p$ with $\rho(M)<1$. Let $(b_{n})$ be a divergent. Show that the sequence $(x_n)$ is divergent, where $x_n=Mx_{n-1}+b_{n-1}$. Not really ...
0
votes
0answers
41 views

Detail in the shifted QR iteration algorithm

In one explanation of the shifted QR iteration algorithm I've read (p. 537 of "Matrix Analysis and Applied Linear Algebra"), the following proposition is given (without proof): At each step of the ...
1
vote
1answer
24 views

One iteration of forward Gauss-Seidel followed by one iteration of backward Gauss-Seidel

Let $A = D - L - U\in\mathbb{R}^{n\times n}$ be a nonsingular matrix, where $-L$ is the matrix of strictly lower triangular elements and $-U$ is the matrix of strictly upper triangular elements. ...
0
votes
0answers
24 views

If $A = I - P$ where $P\geq 0$ and $\rho(P)<1$ then $A$ is an $M$-matrix

Prove that if $A$ can be written as $A = I - P$ where $P\geq 0$ and $\rho(P) < 1$ then $A$ is an $M$-matrix Attempted proof - Suppose $A$ can be written as $A = I - P$ where $P\geq 0$ and $\rho(P)...
1
vote
1answer
25 views

Existence of a fixed point for a linear stationary iterative method

Suppose you are attempting to solve $Ax = b$ using linear stationary iteration method defined by $$x_k = G x_{k-1} + f$$ that is consistent with $Ax = b$, i.e., for which $f = (I - G)A^{-1}b$. Suppose ...
0
votes
2answers
64 views

Are these statements equivalent about eigenvalues?

I shall show that the zeros of a given function $f_{n+1}$ are the eigenvalues of a tridiagonal matrix $M$. Pay attention that the coefficients of $f_{n+1}$ are also in the matrix $M$. Would it suffice ...
1
vote
1answer
33 views

Eigensolver for Black-box matrix

$\DeclareMathOperator{\diag}{diag}$ Consider the generalized eigenproblem $A\mathbf{x}=\lambda B\mathbf{x}$. When solving PDEs numerically (specifically, I am interested on finding the Dirichlet ...
-3
votes
2answers
33 views

Following number is divisible by [closed]

If $ n = 2009$ , then $N = 2009^n -1982^n -1972^n + 1945^n $ is not divisible by 659 1977 1998 2009
2
votes
1answer
42 views

Solve the closed form solution for argmax of $ x^Ty - x^T\ln(x)$

Let $y \in \mathbb{R}^n, \ln(x) = \begin{bmatrix} \ln(x_1) \\ \vdots \\ \ln(x_n) \end{bmatrix} \in \mathbb{R}^n$ Show that $$x^* = \text{argmax}_{x \in \mathcal{D}} \quad x^Ty - x^T\ln(x)$$ ...
1
vote
0answers
34 views

Why does power iteration generate almost dependent vectors?

On the Wiki page for Krylov subspaces: https://en.wikipedia.org/wiki/Krylov_subspace it states given a matrix $A$ and vector $b$, that the vectors $b, Ab, A^2b, A^3b, ...$ "soon become almost linearly ...
2
votes
4answers
114 views

How to prove $I-BA$ is invertible [duplicate]

Show that $I-BA$ is invertible if $I-AB$ is invertible. And also, we have to prove that eigenvalues are same for $AB$ and $BA$ Till now, I used the equation $(I-AB)(I-AB)^{-1}=I$ which gives $(I-AB)...
-2
votes
1answer
24 views

computational cost power matrix $A^k$

Can you help me? If $A\in\mathbb{R}^{n\times n}$, which it is the computational cost $A^{k}=A\cdot A\cdot\ldots\cdot A$?
0
votes
0answers
28 views

Workability of linear equation solving methods for different fields?

So far, I have mostly done linear algebra over $\mathbb R$ and $\mathbb{C}$. I know there exist very many methods to solve equation systems for those fields, of which a few are Gaussian Elimination, ...
2
votes
1answer
69 views

Efficient way to check if a large matrix is positive definite.

Suppose I have a large $n\times{}n$ matrix with $n>1000$ say. I would like to find the quickest way to check if it is positive definite. My matrices are sparse so at the moment I am using sparse ...
0
votes
1answer
33 views

Effects of Scaling on Matrix Norms

I feel as though is a very stupid question, but I'm struggling to muddle through it so here I am. For Gauss-Seidel methods one way to formulate the convergence requirement is that given the system $...
-1
votes
1answer
40 views

Solve $a-1.73d=0, b-1.73d=0, c-1.73d=0, a+b+c -1.73d=0$ [closed]

How can we find nontrivial solutions of the homogeneous equation $$a-1.73d=0, b-1.73d=0, c-1.73d=0, a+b+c -1.73d=0$$ I need to find the values of $a,b,c$ and $d$. When I tried with Gauss ...
0
votes
1answer
11 views

Stochastic matrix relating to power method

I dont quite understand this question that I am doing some practice questions for and was wondering if someone could help explain it. The question is a s follows: "Let $P$ be the stochastic matrix ...
1
vote
0answers
24 views

What is the opposite of “sparsity” in a matrix?

If a sparse matrix has only 1% non-zero entries, I find it weird to speak of "1% sparsity". In particular, "increasing sparsity" goes along with a smaller percentage of non-zero entries, so this is ...
1
vote
1answer
26 views

Derivative of Lattice Laplacian

The lattice Laplacian is defined as, $$ \nabla_L^2x_j \equiv \frac{x_{j+1} - 2x_j + x_{j-1}}{a^2} $$ where the lattice spacing, $a$, is a constant. The derivative, with respect to $x_i$, then gives, ...
1
vote
0answers
31 views

Directly solving non-square subproblem of linear system

I have a large sparse linear system $$\begin{pmatrix} A & B\\ C & D \end{pmatrix} \begin{pmatrix} x\\ y \end{pmatrix} = \begin{pmatrix} f \\ g \end{pmatrix}$$ which ...
0
votes
2answers
62 views

Understanding power method for finding dominant eigenvalues

The power method aims to find the eigenvalue with the largest magnitude. Does magnitude still have the same meaning in this context? If so, can't we tell from the outset which eigenvalue is the ...
1
vote
1answer
37 views

How was this least squares polynomial obtained (solution provided)

Obtain a least squares polynomial of degree 2. $$ \begin{array}{c|lcr} x & \text{0} & \text{0.25} & \text{0.5}& \text{0.75}&\text{1} \\ \hline y & 2.9646 & 3.1826 & 3....
0
votes
0answers
14 views

Why Gauss-Seidel iteration is a projection method

Yousef Saad's iterative method for sparse linear systems says Jacobi, GS, SOR are all projection methods. for example GS is a projection method with $\mathcal K= \mathcal L =\{e_i\}$ (project on $\...
0
votes
1answer
30 views

Preconditioner operator

hope you can help me. I have learned that a preconditioner is a matrix $P$ such that when it is applied to a system $A \mathbf{x} = \mathbf{b}$, the spectral properties of the matrix $P^{-1} A$ are ...
0
votes
1answer
22 views

Preconditioning : ILU($\emptyset$) factorization and SSOR relation?

Let's suppose we have a matrix A = D - L - U , where D,L,U are diagonal , strictly lower and strictly upper triangular,respectively. Generally the preconditioning matrix, according to SSOR(Symmetric ...
2
votes
2answers
88 views

Cholesky decomposition of a covariance matrix with swapped order of variables

Could you please let me know if there is a quick way to recompute result of a Cholesky decomposition of a covariance matrix, if the order of variables was switched to put a different variable as #1 on ...
1
vote
0answers
34 views

Sensitivity of Eigenvalues with invertibte matrix

Let $A$ a matrix having a set of eigenvectors $\{v_1,\ldots,v_n\}$ linearly independent with $\{\lambda_1,\ldots,\lambda_n\}$ eigenvalues associated. Let $\lambda$ eigenvalue of the perturbed matrix $...
1
vote
1answer
20 views

Matrix similar and unitarily diagonalizable

Let $A,B \in R^{n \ x \ n} $ similar and unitarily diagonalizable. Prove that there $Q$ unitarily such that $Q^{H}AQ=B$
3
votes
0answers
44 views

SVD as a solution to linear least squares

I'm a little confused about the various explanations for using Singular Value Decomposition (SVD) to solve the Linear Least Squares (LLS) problem. I understand that LLS attempts fit $Ax=b$ by ...
1
vote
1answer
43 views

Task with using of A Linear Operator

Population of slithy toves living in severe and adverse conditions, subject to the following rules: a) On average, only half toves survive the first year of life, half of the remaining survives in ...
1
vote
0answers
38 views

Create a matrix of four-dimensional space rotate counterclockwise by the angle π / 3 around the plane

Create a matrix of four-dimensional space rotate counterclockwise by the angle $\frac{π}{3}$ around the plane \begin{cases} x − y + t = 0,\\[2ex] y + z + t = 0 \end{cases} on the basis of unit ...
0
votes
1answer
37 views

Undestanding SVM

I am the moment trying to understand how SVM works.. I understand the concept of finding a seperating hyperplane with the highest margin, but i do not understand how it works in mathmatically. Mor ...
0
votes
0answers
25 views

Complex, symmetric linear equations

What is the fastest numerical method to accurately solve complex, symmetric linear equations? Preferably, with a link to a Fortran code. The dimension is about 100-200 variables. To be more explicit, ...
0
votes
1answer
53 views

SVD and Low-rank approximation

In the proof of Low-rank approximation by Trefethen & Bau, It is written: Theorem 5.8 : A is an $m \times n$ Matrix. For every $v$ with $0 \leqslant v \leqslant r$, define $$ A_{v}=\...
1
vote
1answer
44 views

Data structure for a symmetric $n\times n$ matrix

Suppose you are given a symmetric matrix $A\in\mathbb{R}^{n\times n}$ and consider the computation of the matrix vector product $A u \rightarrow v$ where $u\in\mathbb{R}^n$ is given and $v\in\mathbb{R}...