We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [linear-algebra]

The tag has no usage guidance.

51 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1k views

121 views

65 views

77 views

31 views

### Minimize number of math operation of a specific matrix vector multiplication?

Let's say we have a Matrix M and a column vector v like below multiply equals Assume we can only perform multiplication, addition and substraction operation. With normal approach we need 3 ...
32 views

### How is the modular multiplication matrix unitary in Shor's Algorithm?

I have been reading papers about the construction of this matrix in Shor's Algorithm all night. The behavior of the controlled modular multiplication matrix is described as C U_{a^{2}}(|c\rangle|y\...
84 views

### Confusion about the geometric interpretation of the simplex method for linear programming

In Section 7.6.2 of the textbook "Algorithms" by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, the authors provide a geometric interpretation of the two main tasks of each iteration of ...
20 views

### Smallest Circuit for Square of Sparse Symmetric Matrix

I have an n by n symmetric matrix, and I would like to compute its square in as small a circuit complexity as possible. It's sparse: there are sqrt(n) nonzero entries in each row/column, so the input ...
34 views

### Check if no linear combination is within a hypercube

Shapes Let $C$ be the unit hypercube in $\mathbb{R}^{n}$. Let $\vec{o}$ be a point in $\mathbb{R}^{n}$. Let $B$ be a $n \times m$ matrix. The columns of $B$ are a set of linearly independent vectors ...
22 views

### Sparse feasible solution $|x|_0\le k$ for system of linear inequalities $A x \le b$

Suppose the set of linear inequalities $Ax\le b$, in which $A\in\mathbb{R}^{m\times n},x,b\in\mathbb{R}^n$ is given. Is it possible to determine in polynomial time with regard to $m$ and $n$ if there ...
28 views

### Need help implementing an algorithm to solve roots of a transcendental equation

I'm trying to implement this algorithm but I'm having problems reproducing the exemple that it gives a solution to. The general method that I tried is: Make a grid $\theta \in [0,2\pi)$, with say N=...
63 views

### Sparse Matrix inversion without actual inversion

I want to know what are the efficient way to invert a Sparse Matrix? Are there any algorithm,linear algebra or expansions that make this task easier with out actually inverting the matrix? Thank you ...
25 views

### Construct unitary $Q$ such that $span\{q_1,q_2\} = span\{v_1,v_2\}$ where $v_1,v_2 \in \mathbb{R}^n$ are given as input

Assume also that $v_1,v_2$ are linearly independent, and $q_i \in \mathbb{R}^n$ denotes the $i$-th column of $Q$. This is what I've got so far. First obtain unit vectors $w_1,w_2$ which are orthogonal ...
24 views

### Want to do 3D reconstruction via simple matching

I have 2 images, called left and right images. I have some matched points $[c_l,r_l]$ and $[c_r,r_r]$ in both of them (these points are in pixel coordinates). For a 3D point in the real world, they ...
37 views

### Scalability of factor-solve vs. pseudoinverse + product

I’ve always read advice and warnings about the poor scalability and time spent trying to invert a matrix and why it’s better to solve a system of equations whenever the inverted matrix will be used ...
27 views

### Testing whether a set of integers can be written as a combination of module basis elements

Input We are given a set of basis elements, $\ v_1$,$\ v_2$ ,...,$\ v_n$ of a $\mathbb Z^m$- module and a multiset of integers $\ B :=$ {$\ b_1, ..., b_m$} Desired Output Return true if there ...
199 views

### How to solve linear system with modulus operation?

I came across linear equation $G(x,y) = g_k(x,y) l_k(x,y)$ mod $(y^{2^{k}})$ while reading factoring algorithm see section 3 for bivariate polynomials. I need to find the $G(x,y)$ and $l_k(x,y)$. ...
76 views

### Relation between determinant and matrix multiplication

I remember reading somewhere that if matrix multiplication can be done in $O(n^\omega)$ time then determinants can be computed in $O(n^\omega)$ time. I am unable to find the reduction and would it be ...
140 views

### Comparison of matrix determinant in less than $O(n^2)$

I was reading this question and I think maybe somebody here could help. This is the idea: Given a matrix $M$ of integers, and a number $d$ is there a way to compare the determinant of $M$ and $d$ in ...
113 views

### Laplace's Approximation for graphical models

A question about Laplace's approximation: In Laplace's method, we need to find the mode of a function and take second order Taylor's expansion. The first order term will vanish (since the gradient is ...
34 views

### Is this problem in P: Finding a common key for a collection of systems of equations?

Let $B=\{b_1=g_1,\cdots,b_n=g_n\}$ be a set of binary variables $b_i$ and their corresponding values $g_i \in \{0,1\}$. Let $M=\{\sum_{e \in A}e \;:\; A \subset B\}$, i.e., $M$ is the set of all ...
6 views

### Looking for good book similar Stability/Conditioning in Numerical Linear Algebra,

I am currently reading Numerical Linear Algebra by Trefethen and Bau and I am finding it quite difficult to read. In particular, I have been trying to read the sections on Floating Point Arithmetic, ...
22 views

### Check the Complexity time of Power method

Hi i have write a function in Matlab to calculate the power method and i wont to find the time complexity. ...