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

learn more… | top users | synonyms

3
votes
1answer
2k views

What is the operation count for QR factorization using Householder transformations?

I have a hard time finding the operation count of QR factorization when using Householder transformations. The answer is $2mn^2 - \frac{2n^3}{3}$, but have no clue on how to get this count following ...
3
votes
1answer
56 views

Numerical Method Sample Question via Truncation error Methods?

I have one multiple choice question: Approximation of integration $\int_0^{0.1} e^{x^2}dx $ by using simple formula of following options has lower Truncation error: Choice Part: $a)$ ...
2
votes
0answers
36 views

Leading eigenvalues of large sparse unsymmetric matrix

I have a matrix $R$ which is sparse and all eigenvalues are -ve with a zero eigenvalue. Size of R is more than $10^6 \times 10^6$. But I need to calculate only few large (by value not by magnitude) ...
2
votes
0answers
42 views

Efficient way to rigorously learn AI prerequisites

Question: My formal goal is to be able to rigorously understand the mathematical basis for modern statistical learning methods (ML, deep learning). I am told by math people that this involves: linear ...
1
vote
0answers
19 views

statistical comparison, 3 groups, multiple columns

I am using R for some statistical analysis. I have a dataset listing number of deaths by eu regions. the dataset is annual and is for 2000-2008. I divided this data into 4 subgroups according to ...
0
votes
1answer
22 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....
2
votes
1answer
2k views

How to remove linearly dependent rows/cols

How would one remove linearly dependent rows/columns from a rank-deficient matrix. For example, (from wikipedia): $$ A = \begin{bmatrix} 2 & 4 & 1 & 3 \\ -1 & -2 & 1 &...
0
votes
0answers
30 views

why computing x+1 is stable? [closed]

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(...
5
votes
2answers
111 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 ...
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
2answers
33 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
26 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 ...
2
votes
1answer
1k views

Gauss-Seidel method convergence algorithm

From Wikipedia: The convergence properties of the Gauss–Seidel method are dependent on the matrix A. Namely, the procedure is known to converge if either: ...
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 ...
3
votes
0answers
64 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_{...
0
votes
1answer
35 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
20 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, ...
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
35 views

how to project optimal parameters on to feasible region

Hi: I'm trying to understand the concept of projection and I created a toy example that might help me to do that. Suppose that I have a non-linear optimization with 3 parameters theta_1, theta_2 and ...
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 $...
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
1answer
58 views

Iterative methods for solving a linear equation system

There are several methods known for solving a linear equation system Ax = b (like Jacobi or Gauss-Seidel) by iterating $x_{n+1}=Mx_n+c$ with a matrix M, for which some norm is smaller than 1. But ...
2
votes
1answer
1k views

Parallel Algorithms for SVD

I just have completed a preliminar theoretical study of the important SVD decomposition. Now, I'm moving to numerical calculation of SVD. I would like to learn directly a parallel algorithm to ...
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 ...
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
0answers
31 views

Improving my QZ-Algorithm (Include Shifts)

I Need to to solve an generalized Eigenvalue Problem and compare two Methods (QR and QZ) concerning their convergence rate and execution time. I started with the Basic QR-Algorithm, implemented in ...
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
1answer
443 views

How do I find transformation matrix with respect to given basis in the domain and/or the codomain, given the transformation in the standard basis?

I´m being given a linear transformation, for which I can find the standard basis in the domain and codomain; but then, the book ask to find the associated matrix related to a new basis for the domain.....
2
votes
1answer
71 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 ...
1
vote
1answer
34 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
900 views

How to find the Householder transformation?

Assume $x=(1,0,4,6,3,4)^T$. Find a Householder transformation and a positive number $\alpha$ such that $Hx=(1,\alpha,4,6,0,0)^T$. I'm sorry that I don't know how to start with this problem. A ...
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)$$ ...
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)...
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
1answer
58 views

Solving the linear system $XL + L^TX = M$ efficiently

I'm wondering of an efficient way to solve the following system for the symmetric matrix $X$, given a positive semi-definite matrix $S$ and any matrix $M$: $$ LL^T = S $$ $$ XL + L^TX = M $$ $$ (XL) + ...
1
vote
2answers
292 views

Numerical range of a matrix contains the convex hull of the eigenvalues.

I am stuck with the following question. Question: Let $A \in \mathbb{C}^{m \times m}$ be arbitrary. Let $W(A)$ be the numerical range i.e. the set of all Rayleigh quotients of $A$ corresponding to a ...
0
votes
0answers
29 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
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
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 $...
2
votes
2answers
186 views

compute the bisecting normal hyperplane between two $n$-dimensional points.

I have two points $\mathbf{x_1}$ and $\mathbf{x_2}$, where $\mathbf{x_i}=\{x^i_1, x^i_2, \ldots, x^i_n\}$. I need to find a normal hyperplane $P$ that goes through the midpoint of $\mathbf{x_1}$ and $\...
-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
1answer
27 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
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
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
64 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 ...